《数据结构与算法》期末练习题1
- 格式：doc
- 大小：130.37 KB
- 文档页数：9
一、选择：(每题2分，共30分) 简单选择排序 冒泡排序 归并排序 稳定1、下列排序算法中，其中（ ）是稳定的。
堆排序 希尔排序 快速排序 基数排序 不稳定A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序 2、下列排序方法中，哪一个是稳定的排序方法？（ ）A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2 4、非空循环链表head 的尾结点 *p 满足下列( )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 5、下列编码中属前缀码的是( )A){1,01,000,001} B){1,01,011,010} C){0,10,110,11} D){0,1,00,11} 6、对于哈希函数H(key)=key % 7,被称为同义词的关键字是( )A)36和50 B)23和39 C)15和44 D)25和517、将一个长度为n 的向量的第i 个元素删除时，需要前移( )个元素。
A) i B) n-i C) n+1 D) n-i+18、有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找62，要经过( )次比较。
A. 3 B. 6 C. 4 D. 5 9、高度为 K 的二叉树最大的结点数为（ ）。
A)2k B)2k-1 C)2k -1 D)2k-1-110、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )A) (n-1)/2 B) n/2 C) (n+1)/2 D) n11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim 算法 D)拓扑排序算法12、已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( )。
A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 213、一个循环顺序队列 ,队头、尾指针的值分别为front,rear ，则队列中元素个数为( )。
（maxlen 为循环顺序表的长度）A) (rear-front+maxlen) % maxlen B) (rear-front) % maxlen C) rear-front+1 D) front-rear+114、一棵具有 n 个结点的完全二叉树的树高度（深度）是（ ）A)⎣logn ⎦+1 B)logn+1 C)⎣logn ⎦ D)logn-1 15、下面给出的四种排序法中( )排序法是不稳定性排序法。
A) 插入 B) 冒泡 C) 二路归并 D) 快速排序 二、填空题：(每空2分，共20分)1、深度为9的完全二叉树最多有 511 个结点。
2、已知二叉树后序为DGEBFCA ，中序为DBGEACF ，则前序一定是 ABDEGCF1 2 3 43、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(75 66 48 29 31 37)。
4、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值11，需做的关键码比较次数为45、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：________98 99_6、在AOE-网中，设e(i)和l(i)分别表示活动i a的最早开始时间和最晚开始时间，则当且仅当_____e(i)=l(i)____________时，ia为关键活动。
7、下面程序段的时间复杂度为 o(n2) 。
（用O估计）FOR i:=1 TO n DOFOR j:=i TO n DOs=s+j;8、后根遍历树林正好等同于按后序遍历对应的二叉树。
9、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为 6 9 11 1210、n个顶点的连通无向图，其边的条数至少为____n-1____________________。
三、解答题：(每题6分，共30分)1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ和BCDAFEHJIG，试给出该二叉树的后序序列并绘出该二叉树对应的森林。
后序序列为：DCBFJIHGEA2、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。
AB CD E FG H I(I 为f左子树e为叶子)3、在二叉平衡检索树（AVL树）的调整中，将最靠近新插入点的不平衡结点调整平衡后，树中是否还会有不平衡结点？为什么？不会再有不平衡点。
因为插入结点发生不平衡现象后，会改变以“靠近新插入点的不平衡结点”为根的子树（即最小不平横树）的高度加1，经过调整后使最小不平衡树的整体高度又恢复到原来的值，所以不会对原平衡树的其他部分造成危害，因此不会再有不平衡点。
4、某通讯系统只可能有A、B、C、D、E、F 6种字符，0.11，试画出相应的哈夫曼树，并设计哈夫曼编码。
10060 4025 35 B14 11 16 194 10 F D EC A5、指定Hash函数H(k)=3*k mod 1122，41，53，46，30，13，01，67）构造Hash5、解：字母对应编码出现频率A 0001 0.1B 1 0.4C 0000 0.04D 010 0.16E 011 0.19F 001 0.11插入元素后的分布情况：0 1 2 3 4 5 6 7 8 9 1022 41 30 01 53 46 13 67四、算法题：(每题10分，共20分)1、编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都为空或都只有一个结点，要么它们的左右子树都相似。
int Similar(BiTree p,q) //判断二叉树p和q是否相似{if(p==null && q==null) return (1);else if(!p && q || p && !q) return (0);else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar2、下表列出了某工序之间的优先关系和各工序所需时间，要求：（1）画出AOE网（2）列出各事件的最早、最晚发生时间（3）找出该AOE网中的关键路径，并回答完成该工程所需要的最短时间。
工序代号所需时间先驱工序工序代号所需时间先驱工序A 15 无H 15 G、IB 10 无I 120 EC 50 A、B J 60 ID 8 B K 15 F、IE 15 C、D L 30 H、J、KF 40 B M 20 LG 300 E（2）各事件的最早最迟发生时间:事件编号 1 2 3 4 5 6 7 8 9 10 11ve(i) 0 15 10 65 50 80 200 380 395 425 445vl(i) 0 15 57 65 380 80 335 380 395 425 445(3)通过上表不用求出活动的最早最迟开始时间就可以看出关键路径为：1，2，4，6，8，9，10，11完成工程所需的最短时间为：445一、选择：(每题2分，共30分)1、关键路径是事件结点网络中（）。
A)从源点到汇点的最长路径 B)从源点到汇点的最短路径C)最长回路 D)最短回路4、非空循环链表head 的尾结点p 满足下列( )条件。
A. head->next==pB. head==pC. p->next==headD. p->next==nil7、将一个长度为n的向量的第i 个元素删除时，需要前移( )个元素。
A) i B) n-i C) n+1 D) n-i+19、已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作( )。
A) p→next:=p→next→next; B) p→next→next:= →.next;C) p→next:=s; s→next:=p→next; D) s→next:=p→next; p→next:=s;11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）A)深度优先搜索算法B)广度优先搜索算法C)求最小生成树的prim算法D)拓扑排序算法12、从下列有关树的叙述中,选出正确的叙述（）A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B)当K≥1时高度为K的二叉树至多有2k-1个结点。
C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
D)在二叉树中插入结点,该二叉树便不再是二叉树。
五、填空题：(每空2分，共20分)1、树中结点的最大层次称为树的__高度或深度______。
3、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front和rear，且队头指针所指的单元闲置，则队满的条件是_（rear+1）%m==front___，队空的条件是_rear==front______。
六、解答题：(每题6分，共30分)1、在具有n个结点的K（k>=2)叉树的K叉链表表示中，有多少个空指针。
2、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。
AB CD E FG H I(I 为f左子树e为叶子)3、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,分别写出以第一个记录为基准得到的前三次划分结果。
40 38 46 56 79 84 38 40 46 56 79 84 38 40 46 56 79 844、下图是带权的有向图G的邻接矩阵表示，请给出：A、其邻接表存储结构B、按Floyd算法求所有顶点对之间最短距离的矩阵变化过程。
V1 V2 V3 V4V1| 0 1 ∞ 4V2| ∞0 9 2V3| 3 5 0 8V4|∞∞ 6 0AV1->v2 1->v4 4^V2->v3 9->v4 2^V3->v1 3->v2 5->v8 8^V4->v3 6->v4 0^5、判断下列二叉树是否为二叉搜索树，如果是，是否为AVL树，依次插入22、4、1，并对此表作相应的调整。
