青岛科技大学考研专业课试题2008-数据结构.doc

1、青 岛 科 技 大 学二OO八年硕士研究生入学考试试题考试科目：数据结构 注意事项：1本试卷共 4 道大题（共计 41 个小题），满分150分；2本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；3必须用蓝、黑钢笔或签字笔答题，其它均无效。 一、选择题（总分：40分，每小题2分）1、以下与数据的存储结构无关的术语是（ ）。A循环队列 B. 链表 C. 哈希表 D. 栈2、在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( ) 。A. n-i+1 B. n-i C. i D. i-1 3、为查找某一特定

2、单词在文本中出现的位置，可应用的串运算是( ) 。A. 插入 B. 删除 C. 串联接 D. 子串定位 4、下面算法的时间复杂度为( )。 int f( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f(n-1); A. O(1) B.O(n) C. O(n2) D.O(n!) 5、三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A345的存储地址为( )。 A. 356 B. 358 C. 360 D. 362 6、下列陈述中正确的是( ) 。A.二叉树是

3、度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 7、假定一棵三叉树的结点数为50，则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6 8、已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( )。 A. adbefc B. adcefb C. adcbfe D. adefcb 第 1 页（共 5 页）9、ALV树是一种平衡的二叉排序树，树中任一结点的( ) 。A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.

4、左子树的高度均小于右子树的高度 10、给定一个整数集合3，5，6，9，12，下列二叉树哪个是该整数集合对应的哈夫曼（Huffman）树 ( )。11、在含有n个结点的二叉树二叉链表中有（ ）个空链域。A. n B. n-1 C. n+1 D.（n+1）/212、一个栈的输入序列为123n，若输出序列的第一个元素是n，输出的第i（1=i=n）个元素是（ ）。A. 不确定 B. n-i+1 C. i D. n-i13、适用于折半查找的表的存储方式及元素排列要求为( ) 。A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序14、折半查找的时间复杂性为

5、（ ）A. O（n2） B. O（n） C. O（nlog n） D. O（log n）15、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。A. 选择 B. 快速 C. 希尔 D. 冒泡16、设a，b为二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙17、n个顶点的强连通图至少有( )条边。 An B. n-1 C. n+1 D. n（n-1）18、静态链表中指针表示的是（ ）。A 内存地址 B数组下标 C下一元素地址 D左

6、、右孩子地址19、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归 第 2 页（共 5 页）二、填空题（总分：30分，每空2分）1、若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_；而下列程序段的时间复杂性的量级则为 。for(i=0;in;i+)for(j=0;jn,则结点i无 ；若2i+1n，则结点i无 。4、经过下列运算后StackTop(s)的值是 ：InitStack(s);Push(

7、s,a);Push(s,b);Pop(s)。5、对称矩阵的下三角元素ai,j，存放在一维数组vk中，k与i,j的关系是k 。6、在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。查找关键字最多比较的次数 。7、对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_。8、已知一个图如下所示，该图最小生成树中各边权值之和为 _ ，在该图的最小生成树中，从顶点1到4的路径为 。12654320101166181014599、下列程序中所描述函数f的功能为：判断字符串s 是否对称，对称则返回1，否则返回0；如 f(ab

8、ba)返回1，f(abab)返回0；请完成填空，满足功能要求。 int f(1)_) int i=0,j=0; while (sj)(2)_; for(j-; ij & si=sj; i+,j-); return(3)_) 三、应用题（总分：40分）1、（8分）什么是数据结构？数据结构有哪几类基本结构？设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。2、（7分）简述单链表中设置头结点的作用；写一个算法实现建立一个带头结点的单链表，注意先用文字说明算法的思想。第 3 页（共 5 页）3、（4分）画出广义表L=(a,( ),b),(e

9、) 的存储结构图，并利用取表头和取表尾的操作分离出原子e。4、（4分）画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。5、（6分）给出下图：（1）画出图的邻接表表示图；（2）根据你画出的邻接表，以顶点为根，画出图的深度优先生成树和广度优先生成树。31057842169 6、（6分）阅读下列算法，并回答下列问题： (1)、该算法采用何种策略进行排序? (2)、写出用此种排序方法对关键字序列49，38，65，97，76，13，27排序的过程。 void Sort ( SqList &L ) for ( i=2; i=L.le

10、ngth; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri; for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1 = L.rj; L.rj+1 = L.r0; 7、（5分）设有一组关键字9，01，23，14，55，20，84，27，采用哈希函数：H(key)=key MOD 7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) MOD 10（di=12，22，32，）解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。四、算法设计题（总分：40分）（要求首先用文字

11、描述算法思想，然后用类c的语言写出算法）。1、（6分）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。2、（8分）函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数。第 4 页（共 5 页）3、（6分）假设二叉树T采用如下定义的存储结构： typedef struct node DataTy

12、pe data; struct node *lchild,*rchild,*parent; PBinTree; 其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。4、（10分）采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。5、（10分）二叉排序树采用二叉链表存储。编写算法，删除结点值是X的结点，要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长（可不考虑被删除的结点是根的情况）。第 5 页（共 5 页）