科目代码： 407 科目名称： 数据结构 (共4页)
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（本大题共15道小题 ，每小题3分，共45分）
1．若解决某个问题有两个算法X和Y，其中X的时间复杂度为T(n)=O(n)，Y 的时间复杂度为T(n)=O(log2n)，就时间复杂度而言，哪个更好？ 【 】 A. 算法X好于算法Y B. 算法Y 好于算法X C. 不确定 D. 其实两个算法一样 2．由两个栈共享一个向量空间的好处是： A． 减少存取时间，降低上溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C．减少存取时间，降低下溢发生的机率 D. 节省存储空间，降低下溢发生的几率
3．一个广义表的表头 【 】 A． 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子
4. 某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序序列为 【 】 A. CEDBA B. DECAB C. DEABC D. ACBED
5. 在下列的排序方法中，最耗费内存量的是 【 】 A. 插入排序 B 快速排序 C. 选择排序 D. 归并排序
6. m阶B_树中所有的非叶子（除根之外）结点中的关键字个数必须大于或者等于 【 】 A. m/2 B. m/2－1 C. m/2 D. m/2－1
7．已知一个有序表为｛3,5,7,8,11,15,17,22,23,27,29,33｝，当采用二分查找法查找值为27时，需要比较几次才能查找成功？ 【 】 A．4 B. 3 C. 10 D. 不确定
8．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为 【 】 A．e B. 2e C. n2－e D. n2－2e
9．为了采用动态查找表进行高效率的查找，数据的组织结构最好采用 【 】 A．有序表 B. 线性链表 C. 二叉排序树 D. 分块有序表
10．若一棵二叉树有21个结点，且无度为1的结点，则叶子结点的个数为 【 】 A．9 B. 10 C. 11 D. 12
11. 设计一个好的哈希函数，其函数值应该以什么概率取其值域的每个值。 【 】 A．同等概率 B. 随机概率 C. 最大概率 D. 最小概率
12. 下列排序方法中，其比较次数与待排序关键字的初始状态无关的是 【 】 A. 冒泡排序 B. 二分法插入排序 C.快速排序 D. 直接插入排序
13. 已知广义表Glist＝((a),(b,c,d),((e)))，使用head和tail函数取出Glist中原子b的运算应是 【 】 A. head(head(Glist)) B. tail(head(Glist)) C. head(head(tail(Glist))) D. head(tail(Glist))
-
- 1 - -
14. 用邻接表表示图进行广度优先遍历时，通常采用哪种结构实现算法。 【 】 A. 栈 B.队列 C.二叉树 D.图
15. 设哈希表长m=14，哈希函数H(K)=K%11。表中已有四个关键字，如果使用二次探测再散列处理冲突，关键字为49的存储地址为 【 】
0 1 2 3 4 5 6 7 8 9 10 11 12 13 17 33 8 21 A. 3 B. 5 C. 8 D. 9 二、填空题（本大题共10小题，每题2分，共20分）
1. 在循环链表中，可根据任意结点的地址遍历整个链表，而单链链表则知道__________才能够遍历整个链表。
2. 在顺序表中，访问任一结点的时间复杂度为__________。
3. 设循环队列的空间大小为MAX，当rear 7. AOV网的拓扑序列_______唯一的。 8. 在各种查找方法中，平均查找长度与关键字个数n无关的查找方法是________。 9. 设一组记录的关键字为｛45, 80, 55, 35, 40, 85｝，则利用快速排序的方法，以第一个关键字为基准，得到的一次划分结果为______________________。 10. 设一组记录的关键字为｛45, 80, 55, 35, 40, 85｝，则利用堆排序的方法，建立的初始大根堆为_______________________。 三、解答题（本大题共4道小题，每小题10分，共40分） 1. 就顺序队列中的“假溢出”现象，请给出解决它的思想及队空、队满的判断问题。 2. 对给定的关键字集合，以不同的次序插入初始状态为空的树中，是否可以得到同一棵二叉排序树？试给出一个具体的例子证明你的结论。 3. 已知关键字序列为｛Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec｝，试回答： (1) 按表中元素的顺序，构造一棵平衡二叉排序树。 (2) 在等概率的情况下，求查找成功的ASL值。 4. 已知一个带权的连通图G(V, E)的邻接表如下图所示。请回答： (1) 画出该图。 (2) 从顶点V2出发，给出DFS序列。 (3) 从顶点V3出发，给出BFS序列。 (4) 画出该图的一棵最小生成树。 - - 2 - - 顶点号 边上的权值 指针 1 11 2 14 0 V0 0 11 2 2 1 V1 2 V2 0 14 1 2 3 V3 0 17 2 4 3 4 3 4 17 ^ 21 ^ 4 ^ 10 ^ 4 V4 1 21 3 10 ^ 四、算法阅读题（本大题共2道小题，每题12分，共24分）【说明】 结构定义 struct ListNode { elemtype data; struct ListNode *next; }; struct BTreeNode { elemtype data; struct BtreeNode *lchild, *rchild; }; 1. 下面的是对某个带头结点的单链表的操作，试说明得法的功能。 Void DSNode(ListNode *head) { ListNode *p, *q, *r; p = head->next; while(p){ q = p; r = q->next; do{ while( r && r->data != p->data){ q= r; r= r->next; } if(r){ q->next = r->next; delete r; r = q->next; } } while(r); p = p->next; } } - - 3 - - 2. 下面的算法是一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。请在空白处填入正确的语句。 Void DoubleBubble{int a[], int n} { int i=0, j, temp, exchange =1; while(exchange){ exchange=0; for(j=n-i-1;j>i;j--) if(a[j] exchange =_________; temp = a[j]; ___________; a[j+1]=temp; } j++; } } 五、算法设计题（本大题共3道小题，每道7分，共21分） 1. 设单链表中存放着若干个字符，试设计算法判断该字符串是否中心对称。例如ABCBA、ABCCBA都是中心对称的字符串。 【要求】 必须使用栈结构。 int isSymmetry(struct ListNode *head) { 2. 以单链表为存储结构，试编写一个直接选择排序算法。 【要求】 (1)说明直接选择排序的思想。 (2)给出算法。 Void SelectSort(struct ListNode *head) { 3. 证明：对一个长度为n的任意顺序表进行排序，至少需要进行nlog2n次比较。 - - 4 - - 因篇幅问题不能全部显示，请点此查看更多更全内容