1、第1页共 8页三 峡 大 学2012年研究生入学考试试题(A卷)科目代码： 838 科目名称： 数据结构 （考生必须将答案写在答题纸上，总分150分，考试时间180分钟）一、选择题 (每小题 2分，共 40 分)1、线性表采用链式存储时，结点的存储地址（ ）。A. 必须是不连续的 B. 连续与否均可C. 必须是连续的 D. 和头结点的存储地址相连续2、已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行（ ）操作。A. s-next=p-next; p-next=s B. q-next=s; s-next=p C. p-next=s-next; s-next=
2、p D. p-next=s; s-next=q3、设有一个顺序栈S, 元素按S1, S2, S3, S4, S5, S6顺序进栈，若6个元素的出栈顺序为S2, S3, S4, S6, S5, S1, 则顺序栈的容量至少应为（ ）。A. 2 B. 3 C. 4 D. 54、如下陈述中正确的是（ ）。A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母 D. 空串就是空白串5、设有一个二维数Amn，假设A00存放位置在544，A55存放位置在624，每个元素占一个空间，A22在（ ）位置。A. 592 B. 586 C. 576 D. 6086、设有5个字符出现的频度分别为
3、1,2,3,5,4，则对应的哈夫曼树的带权路径长度为（ ）。A. 34 B. 33 C. 35 D. 157、 含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（ ）。A. e B. 2e C. n2-e D. n2-2e第 2 页8、 长度为500的有序表采用折半查找时，查找成功最大比较次数为（ ）。A. 8 B. 9 C. 10 D. 119、快速排序在下列哪种情况下最易发挥其长处（ ）。A. 被排序的数据中含有多个相同排序码 B. 被排序的数据已基本有序C. 被排序的数据完全无序 D. 被排序的数据中的最大值和最小值相差悬殊10、下列关键字序列中，（ ）是堆。A. 16, 72,
4、31, 23, 94, 53 B. 94, 23, 31, 72, 16, 53 C. 16, 53, 23, 94，31, 72 D. 16, 23, 53, 31, 94, 7211、 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1, p2, p3, , pn,若p1=n，则pi为（ ）。A. i B. n = i C. n-i+1 D. 不确定12、具有n(n0)个结点的完全二叉树的深度为（ ）。A. log2 (n) B. log2 (n) +1 C. log2 (n) +1 D. log2 (n) -113、在一个图中，所有顶点的度数之和等于图的边数的多少倍（ ）。A. 1
5、/2 B. 1 C. 2 D. 4 14、用邻接表表示图进行广度优先遍历时，通常是采用（ ）数据结构 来实现算法的。A. 栈 B. 队列 C. 树 D. 图 15、深度优先遍历类似于二叉树的（ ）。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历16、有8个结点的无向图最多有（ ）条边。A. 14 B. 28 C. 56 D. 11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败。（ ）A. 20，70，30，50 B. 30，88，70，50 C. 20，50 D. 30，8
6、8，50第 3 页18、任何一个无向连通图的最小生成树（ ）。A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在19、链表适用于哪种查找（ ）。A. 顺序 B. 二分法 C. 顺序，也能二分法 D. 随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（ ）。A. 是唯一的 B. 有多种C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子二、填空题(每小题 1 分，共 30分)1、对于一个表长为n的顺序表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。（要求用大O表示法表示）2、神枪手依次压入10颗子弹进入枪膛，编号分别为1-1
7、0，则消灭第4个敌人的子弹编号是 。3、已知一采用空闲单元法的循环队列容量为20，队列的首、尾指针分别用f和r表示，f3，r18时队列的长度为 ，f15，r7时队列的长度为 。 4、设有一个10阶的对称矩阵A1010，每个数据占2个字节，A00的存储地址是24，则A38的地址是 ，若采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B中，A00存入B0中，则A85在B中的下标是 ，A58在B中的下标是 。5、一棵深度为6的满二叉树有 个分支结点和 个叶子结点。6、 是被限定为只能在表的一端进行插入和删除运算的线性表。7、已知某二叉树的中序遍历结果是：DEBAC，后序遍历结果是：EDBCA
8、，则该树的先序遍历序列是 ，层序遍历序列是 。8、若采用基于二叉树的递归遍历方法编写建树和销毁树的函数，那么建树应该基于 遍历函数修改，而销毁树应该基于 遍历函数修改。 9、稀疏图适合采用 存储结构，其对应的最小生成树算法是基于 归并的，最好用 算法来求解。第 4 页10、假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。11、设数组a160, 170的基地址为2048，每个元
9、素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。12、如果一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。13、GetHead【GetTail【(a,b),(c,d)】= 。14、写出下列程序段的时间复杂度，要求用大O表示法表示。s=0; i=1; for i=0; in; i+) while(i=n)for(j=0; jlchild); if( !root-lchild & !root-rchild ) x+; if( !root-lchild | !root-rchild )
10、 y+; ABC (root-rchild); （1）该算法是在二叉树哪种遍历程序基础上修改成的？（2分）（2）执行该算法后x和y中保存的值分别是什么？ （3分）（3）试用x和y表示二叉树的总结点数n。 （3分）2、阅读程序，回答问题。（12分）（1） void proc_1(adjlist GL, int i, int n) printf(“%d”,i); visitedi=true; edgenode *p=GLi; while (p!=NULL) int j=p-adjvex; if( ! visitedj ) proc_1 (GL,j,n); p=p-next; 第 7 页该函数实现的
11、是( )的( )操作，采用的存储结构是( )，算法执行时系统内部需要调用( )数据结构。（4分）（2） void proc_2(Stack S, int e)Stack T; int d;InitStack(&T);While(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push( &T, d);While(!EmptyStack(T) Pop(&T, &d); Push( &S, d);简述proc_2的功能。（4分）（3） void proc_3(Queue *Q)Stack S; int d;InitStack(&S);While(!EmptyQueue(
12、* Q) DeleteQueue(Q, &d); Push( &S, d);While(!EmptyStack(S) Pop(&S, &d); EnterQueue( Q, d);简述proc_3的功能。（4分）第 8 页3、算法填空，使之可以对降序序列进行二分查找,要求找到则返回元素在查找表中位置，否则返回0。（10分）int binarysearch( splist st ,int n , keytype key) /降序序列函数，st顺序表 n表长 key 关键字int mid ,low,high,find;find=0; low=1; high=n;while ( (lowstmid.key) (2) ;else if (keystmid.key) (3) ;else (4) ; /找到printf(“find st%d.key= =%dn”,mid,key); (5) ;/返回if (find= =0)return(0); /*binarysearch二分查找*/
