1、共 8 页， 第 1 页 上 饶 师 范 学 院 自 测 试 题 三 课程名称： 数据结构 适用学期：第 四 学期适用专业： 计算机科学与技术 适用层次： 本 科 班级： 学号： 姓名 题号 一 二 三 四 五 六 七 总分得分阅 卷 教师 签 名一、 选择题(每小题 2分，10 小题共 20分)1评价算法优劣的两个主要方面是( )。A. 时间复杂性和空间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性2. 冒泡排序(起泡排序)的时间复杂性为( )。A. O(n) B. O(nlogn) C. O(logn) D. O( )2n3用 10 万个无序且互不相等的正整
2、数序列，采用顺序存储的方式组织，希望能以最快的速度找出前 10 个最大的数字，采用( )方法较好。A. 快速排序 B. 起泡排序 C. 直接选择排序 D. 归并排序4二分查找法的时间复杂度为( )。A. O(n) B. O(nlogn) C. O(logn) D. O( )2n5. 设串 s1 = “ABCDEFG” , s2 =“PQRST” ，函数 concat(x,y)返回 x和 y 串的连接串，subStr(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，length(s)返回串 s 的长度，则 concat(subStr(s1,2,length(s2),su
3、bStr(s1,length(s2),2)的结果串是( )。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF6. 若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点数为( )。A. 9 B. 11. C. 12 D. 不确定7线性表的链表存储结构与顺序存储结构相比的优点是( )。 得分共 8 页， 第 2 页 A. 所有的操作算法简单 B. 便于随机存取C. 便于插入和删除 D. 便于查找操作8树的基本周游(周游)策略可分为先根周游和后根周游，二叉树的基本周游策略可为为先序周游、中序周游、后序周游，这里，我们把由树转化得到的二叉树叫做这棵树
4、对应的二叉树，以下结论中( )是正确的。A. 树的先根周游序列与其对应的二叉树的先序周游序列相同；B. 树的后根周游序列与其对应的二叉树的后序周游序列相同；C. 树的后根周游序列与其对应的二叉树的中序周游序列相同；D. 树的先根周游序列与其对应的二叉树的中序周游序列相同；9一个栈的输入序列是 1，2，3，4，5，则栈的不可能的输出序列是( )。A. 54321 B. 45321 C. 45312 D. 12345 10. 已知一个有向图如右所示，则从顶点 a 出发进行深度优先周游， ，不可能得到的 DFS 序列为( )Aa d b e f c B. a d c e f b C.a d c b
5、f e D. a d e f c b二、 填空题(每小题 2分 8小题共 16分)11数据结构是相互间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容（三个要素） ，分别是数据的逻辑结构、 、 。12规定树的根结点的层数为 0，树中结点的最大层数为树的深度，深度为 K的完全二叉树至少有 个结点，至多有 个结点。13在 n 个结点的单链表中，在 P 指向的结点之后插入一个结点的时间复杂度为_。14在对一组记录54，38 ，96，23，15，72，60，45，83 进行堆排序时，根据初始记录构成初始堆（大根堆）后，最后四条记录为 。15图的存储结构主要有两种表示法： 和 。16插入操作可
6、以在线性表的 位置进行，可以在栈的 进行，可以在队列的 进行。得分共 8 页， 第 3 页 17在散列存储中，一般情况下，负载因子 的值越大，存取元素时发生的冲突就越 ，负载因子 的值越小，存取元素时发生的冲突就越 。在散列查找中，平均查找长度除与 有关外，还与 和 有关。 18设 a=”101JF+109JF”， t=”102JF”，q=”101QMDF”，则 subStr(a,7,3)为 ， index(a,JF)的值为 。 三、 概念简答题：(每小题 3分, 共 9分)19. 什么是栈? 举例说明栈有哪些用途（至少 2 种用途） 。20. 解释排序算法中稳定性概念，在所学的排序算法中,
7、哪些是稳定的排序算法？ 21. 什么是最优二叉树(哈夫曼树 )？以2,3,4,11构造哈夫曼树的带树路径长度为多少？四、 简单解答题：（每小题 5分，4 小题共 20分）22. 给出二叉树的对称次序和后根次序列如下：（5 分）对称次序：DBLFEGAHJIKC后根次序：DLFGEBJKIHCA（1）请画出这棵二叉树。（2）请画出这棵二叉树所对应的一般的树或森林。得分得分共 8 页， 第 4 页 23. 若散列表(Hash)的地址范围为 0,9, 散列函数为： ,并9mod)2()keyH采用拉链法处理冲突,请画出元素 7、4、5、3、6、2、8、9 依次插入散列表以后该散列表的状态。24用深度
8、优先搜索周游如下图所示的无向图，试给出以 A 为起点的顶点访问序列25对上题画出用 Kruskal 算法求得的一棵最小生成树。共 8 页， 第 5 页 五、 程序阅读理解填空题(此题共 3小题，共 56617 分)26程序说明：设有二个同数据类型的有序表（元素按键值从小到大排列） ，表 A 和表 B（以带表头的单链表形式存储） ，本程序（算法）判断表 A 是否包含在表 B 中（比如 B（a,c,x,y,z,u） ，A(x,y,z)，则 A 包含在 B 中，若表A 为空表，则 A 包含在 B 中） ，若表 A 包含在表 B 中则返回 true, 否则返回false,判断算法中，采中了递归，若 p
9、a, pb 所指的元素相同（比如 pa 指向 A中的 x 的结点，pb 指向 B 中的 x 的结点） ，则递归调用自己，请填空使其完成所需的功能。 （每空 1 分，共 5 分）typedef enumtrue=1,false=0boolean;typedef struct Node DataType key;strict Node *link;Node, *LinkList;boolean inclusion(LinkList ha, LinkList hb)/*ha,hb 指向带表头的单链表 A、B，注意，A、B 是有序表*/ LinkList pa,pb;pa=ha-link;pb=hb-
10、link;if (pb=NULL) （1） ; /*递归出口条件，如果 pb 所指为空，则 pb 所指的子串包含在 pa 所指的子串中，此时应返回 true;*/while( （ 2） ) /*当 pb 所指非空并且 pa 所指元素键值大于等于 pb 所指元素的键值时*/if (pa-key=pb-key)then( （3） ); /*提示：考虑递归调用，返回递归调用结果：*/else( （4） ); pa 沿单链表往下指一个，从新位置上来寻求是与有与 hb 匹配的子串。（5） ;/*此时已寻找完毕，没有找到与 hb 匹配的子串，应返回结果。*/27程序说明：如下程序实现带插入的二叉排序树的检
11、索：给定一系列字符，输出每个字符出现的次数。为此，从空树开始，在树中检索每一个字符，如果得分共 8 页， 第 6 页 找到，其出现计数加 1，否则就作为一新结点插入。请填充程序，使其完整。（每空 1 分，共 6 分）typedef char KeyType;struct BinTreeNode;typedef struct BinTreeNode *PBinTreeNode;struct BinTreeNodeKeyType key;int count;PBinTreeNode llink,rlink;PBinTreeNode root; int k;void printtree(PBinTr
12、eeNode w, int ln)/*按凹入表的形式打印二叉树，ln 用于对凹入表中每行空格进行控制, 每行先打印 ln 个空格，再打印结点有关信息。*/ int i;if(w!=NULL) for(i=1; ikey,w-count);printtree(w-llink,ln+1);（1） ；/*递归打印右子树*/void seach(KeyType x,PBinTreeNode *q)/*注意，此处，q 为指向指针的指针，即对指针的引用！*/ PBinTreeNode p=*q;if(p=NULL) （2） ； /*申请空间，并让 p 指向该空间。*/p-key=x;p-llink=NUL
13、L;p-rlink=NULL;p-count=1;（3） ；/* 改变*q 所指！*/else if (xkey)seach(x,else（4） ；/*考虑 xp-keyj 时的情况*/共 8 页， 第 7 页 seach(x,else（5） ；main() char ch;while(ch=getchar()!=#)seach(ch,printtree(root,0);28程序说明下列程序是快速排序，请将程序补充完整：（每空 2 分，3 空共 6 分）void quickSort(SortObject *pvector,int l,int r) int i,j;RecordNode temp
14、;If(l=r) return ; /*只有一个记录或无记录，则无需排序*/i=l;j=r;temp= pvector-recordi;while(i!=j) while(pvector-recordj.key=temp.key)if(irecordi.keyi)i+;if(irecordj-=pvector-recordi;（2） ;（3） ；quickSort(pvector,i+1,r) ;六、 综合应用题(18 分)29. 假定用二叉链表表示一棵二叉树；(1)写出二叉链表的结点的类型定义；(4 分)得分共 8 页， 第 8 页 (2)设 root 为指向二叉树的根结点的指针，试写一递归算法，求二叉树中叶子结点的数目，输出结果。(4 分)(3)试写出一个非递归算法，求二叉树中的叶子结点的数目(可以用栈或队列，栈与队列的有关操作不必编程)。输出所有的树叶及树叶总数。(10 分)
