数据结构期末考试试.pdf
1线性链表不具有的特点是(）.A随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比2设一个栈的输入序列为1，2,3,4,则输出序列不可能是（)。A 1,2，3，4 B4,3，2,1 C1，3,2,4 D4,1，2，3 3下列排序算法中,()排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。A归并B冒泡C选择D堆4下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串)。Ada，ax，eb,de，bb ff ha,gc Bcd，eb，ax，da ff ha，gc,bbCgc，ax，eb,cd,bb ff da,ha Dax,bb，cd,da ff eb，gc,ha5设有一个10 阶的对称矩阵A10 10，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B 中，A00 存入 B0中,则 A85在 B 中(）位置。A 32 B33 C41 D65 6。下面哪一种图的邻接矩阵肯定是对称矩阵(）。A有向图B无向图CAOV 网DAOE 网7具有 2008 个结点的二叉树，其深度至少为(）。A 9 B10 C11 D 12 8.关键路径是边表示活动的网(AOE 网）中的().A从源点到汇点的最长路径B从源点到汇点的最短路径C最长的回路D最短的回路9 一个广义表为（a,（a,b)，d，e，（i，j），k）)，则该广义表的长度为（)。A不确定B8 C5 D610设循环队列中数组的下标范围是0n 1，其头尾指针分别为f和 r，则其元素个数为（）。Ar f Br f+1 C（r f)mod n+1 D（r f+n）mod n1算法具有的五个重要特性是：有穷性，确定性,_,输入和输出。2一组记录的关键字为（45，80,55，40，42，85），则利用堆排序的方法建立的初始堆为_.3对如下无向图G，从结点 V1出发，写出一个按深度优先遍历图的结点序列：_。错误!错误!错误!错误!错误!第 3题图，6 第4题图4写出右上图中的一个拓扑有序序列_.5对于顺序存储的线性表,访问结点和删除结点的时间复杂度分别为_。6平衡二叉树上所有结点的平衡因子只可能是_。7假定对线性表R1.。60进行分块查找,共分为 10 块,每块长度等于6。若假定查找索引表和块均用顺序查找的方法，则查找每一个元素的平均查找长度为_。8将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为37 的双亲结点编号为_.9设有一个字符串s=science,其非空子串的数目是_。10有 n 个顶点的强连通有向图G 至少有 _条弧.1 一棵二叉树的先序序列和中序序列分别如下，先序序列：ABCDEFGHIJ 中序序列：CBDEAGIHJF（1）画出该二叉树。（3 分）（2）写出其后序序列。（3 分）2给出用Kruskal 算法构造下列带权图的最小生成树的过程.3 1 5 4 3 4 1 6 2 3.已知一个长度为12 的表（6，8，4，12，2，10,7，3，9，1,11，5)。（1）将表中的元素依次插入到一个初始为空的二叉排序树中,画出该二叉排序树并求其在等概率下的平均查找长度。（3 分)(2)若先对表中的记录排序，构成有序表后再对其进行折半查找,画出判定树并求其在等概率下的平均查找长度.(3分）4已知哈希表地址空间为0。.10,哈希函数为H（key）=key MOD 11,采用链地址法处理冲突,将下面数据序列依次插入该哈希表中,并求出在等概率下查找成功时的平均查找长度。12，24,1，34，38，44,27，22.5假定用于通信的电文仅由8 个字母 a，b，c，d，e，d,f,g，h 组成，各个字母在电文中出现的频率分别为5,23，3,6，10，11，36，4。要求：（1）以这些频率作为叶子结点的权值构造Huffman 树。（2 分)（2）试为这8 个字母设计不等长Huffman 编码.（2 分）A b c d e f g h（3）计算出电文总长度.（2 分）1。有两个不带头结点的单循环链表,链表头指针分别为a 和 b。编写一个过程将链表b 链到链表 a 之后，链接后的链表仍保持循环链表形式。2.试编写一个计算二叉树的叶子结点数的算法。要求二叉树采用链式存储结构。3.请写出监视哨设在高下标端的插入排序算法。06 2 V2V1V3V6V4V5V2V1V3 V4V5 V6 V7V8 1.具有 n（n0）个结点的完全二叉树的深度为（）A.log2nB.log2nC.log2n+1 D.log2n+12.一个栈的进栈序列是a,b，c，d,e,则栈的不可能的输出序列是（）A。abcde B。edcba C。decba D.dceab 3.数据在计算机存储器内表示时，物理地址与逻辑地址相同且连续,称之为（）A。存储结构B。逻辑结构C.顺序存储结构D。链式存储结构4。对二叉排序树的左子树中所有结点与右子树中所有结点的关键字大小关系是(）A。小于B.大于C.等于D.不小于5。按照二叉树的定义,具有 3 个节点的二叉树_种（）A.2 B。3 C.4 D.5 6.广义表（a）的表尾是（)Aa B。(a）C（）D.（(a)7设有两个串p 和 q，求在 q 在 p 中首次出现的位置的运算称为(）A.模式匹配B。连接C。求子串D.求串长8。引入二叉线索树的目的是（)A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一9在有 n 个叶子结点的哈夫曼树中，其结点总数为A。不确定B.2n-1 C.2n D。2n+1 10与单链表相比，双向链表的优点之一是A插入、删除更简单B。可以进行随机访问C可以省略表头指针或表尾指针D。访问前后相邻结点更方便1 Prim 算法适合求 _的网的最小生成树,而 Kruskal 算法适用于求_的网的最小生成树。2。循环单链表L 为空的条件是_。3。在对队列中，新插入的 元 素 只 能 插 入 到 _.4 平 衡 二 叉 树 上 所 有 结 点 的 平 衡 因 子 只 可 能 是_。5一个有序表1，3，9，12，32，41，45，62,75，77，82,95，99，当采用折半查找法查找关键字为82 的元素时，_次比较后查找成功.6设二维数组A610，每个数组元素占4 个存储单元,若按行优先顺序存放数组元素，A00的存储地址是860，则 A3 5的存储地址是_。7可以进行拓扑排序的一定是_。8求单链表长度算法的时间复杂度是_。9。在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是_.1.已知一个二叉树的中序遍历序列为DGBAECF，后序遍历序列为GDBEFCA,请给出:（3）画出该二叉树。（3 分）（4）写出其后序序列.(3 分）对关键字序列11，78，10，1,3，2,4，21构造哈希表，取散列地址为HT0。.10，散列函数为 H（K)K11，试用线性探查法冲突,画出相应的哈希表,并分别求查找成功和不成功时的平均查找长度。3。已知关键字序列503，87,512，61，908,170,897，275，653，462,采用快速排序算法对该序列作升序排序时的每一趟的结果。4。从一棵空树开始，逐个读入并插入下列关键字：40，28,6,72，100,3,54，1,80,91，38请首先建立二叉排序树，然后删除节点72，并给出删除节点72 后的二叉树.5.给定权集W=2,3，4,7,8，9，试构造关于W 的一棵哈夫曼树，并求带权路径长度WPL。1.有一个有序单链表（从小到大排序）,表头指针为L，设计一个算法向该单链表中插入一个元素为 x 的结点，并使插入后链表仍然有序。2。二叉树采用链式存储结构，试编写算法求二叉树的深度。3。二叉树采用链式存储结构，试设计一个按层次顺序（同层自左向右）遍历二叉树的算法。答案A 一、选择题（每小题2 分，共 20 分）1。A2。D 3。A 4。A 5。C 6。B 7。C 8.A 9。C 10。D 二、填空题（每小题2 分，共 20 分）1可行性2（85，80,55，40，42，45）3V1，V2,V3，V5,V4，V6,V7,V8（答案不惟一)41,2,3，5,6,4（答案不惟一）5。O（1）和O（n）6。1，0，1 7。9 8。18 9。26 10n 三、解答下列各题（每小题6 分,共 30 分）1该二叉树为（3 分):A B F C D G E H I J 后序序列：CEDBIJHGFA（3 分）2 V1 V2 V1 V2 V1 V2 1 1 1 V3 V6 V3 V6 V3 V6 1 1 V4 V5 V5 V4 2 V5（2 分)（1 分)(1 分）V1 3 V2 V1 3 V2 1 1 4 V3 V6 V3 V6 1 1 V4 2 V5 V4 2 V5（1 分）（1 分）3（1）二叉排序树为:6 4 8 2 5 7 12 1 3 10 9 11(2 分）等概率下平均查找长度ASL=(1+2*2+3*4+4 3+52)/12=13/4=3.25（1 分）（2）排序后进行折半查找的判定树为：6 3 9 1 4 7 11 2 5 8 10 12（2 分)等概率下平均查找长度ASL=（1+2*2+3 4+45)/12=37/12 3.08（1 分）第 1 页（共 3 页)4哈希函数值为:（1 分)H（12）=1 H（24）=2 H（1)=1 H(34)=1 H（38）=5 H（44）=0 H(27)=5 H（22）=0 哈希表为:（3 分）0 22 44 1 1 12 34 2 24 3 4 5 27 38 6 7 8 9 10 平均查找长度ASL=（14+23+31）/8=13/8=1。625(2 分)5（1）Huffman 树为：(2 分)98 39 59 17 22 23 36 7 10 11 11 3 4 5 6(2）其 huffman 编码为（2 分）注：此题答案不唯一,只要满足哈夫曼编码的要求都可。a b c d E f g H 0100 10 0000 0101 001 011 11 0001（3）电文总码数为45+2*23+4*3+4*6+310+3*11+2*36+4 4=253（2 分）四、算法设计(每小题 10 分，共 30 分）说明：每小题中：1思路正确3 分2算法正确5 分3算法完整2 分（1）typedef struct LNode ElemType data;struct LNode next;LNode,*LinkList;void Connect（LinkList a,LinkList b）/将循环链表b 链在循环链表a 之后的算法，链表a 和 b 均不带头结点LinkList p;p=a;/先令指针p 指向链表a 的第一个结点while（p nexta）p=p next；/找到链表a的最后一个结点pnext=b；/将链表 b 链到 a的最后一个结点之后第 2 页（共 3 页）p=b;/令指针 p 指向链表b 的第一个结点while（p-nextb）p=p-next；/找到链表b 的最后一个结点p next=a;/令链表 b 的最后一个结点指向合并后的链表的表头（2）Typedef struct BiTNode TelemType data；Struct BiTNode lchild，rchild；BiTNode，*BiTree；void leaf(BiTree T)/采用二叉链表存贮二叉树，n 为全局变量，用于累加二叉树的叶子结点/的个数.本算法在先序遍历二叉树的过程中,统计叶子结点的个数/第一次被调用时,n=0 if（T)/若二叉树为空，结束返回/若二叉树不为空,在先序遍历二叉树的过程中，统计叶子结点的个数if(T lchild=null&T-rchild=null）n=n+1；leaf（T-lchild）；leaf(T rchild）；/if/leaf（3）typedef struct KeyType key；InfoType otherinfo；RedType；typedef struct RedType rMAXSIZE+1；int length；SqList；void Insert_Sort1(SqList L）/监视哨设在高下标端的插入排序算法 k=L.length；for（i=k 1；i;i)/从后向前逐个插入排序 if（L.r i.keyL。ri+1。key）L。rk+1。key=L.r i。key；/监视哨 for(j=i+1;L.rk+1。keyL。rj.key；+j）L.r j-1=L.r j；/前移 L。rj1=L。r k+1；/插入/Insert_Sort1 B 一、选择题(每小题 1 分，共 10 分）1-5 C D C B D 610 C A A D D 二、填空题（每空2 分，共 20 分）1.边稠密，边稀疏2.L-next=L;3.队尾4.1，0，1 5.4 6.1000 7.无环图8.O(n）9.快速排序三、解答题（每小题6 分，共 30 分）1。（1)二叉树是:（4 分）（2）后序序列为:GDBEFCA（2 分)2。解：首先求出散列地址，据此得到哈希表见下图。0 1 2 3 4 5 6 7 8 9 10 11 78 1 3 2 4 21 10 查找成功的平均比较次数为：ASL（11213 28l）82。375 查找不成功的平均查找长度为:ASLunsucc（87 6543211 19）11 4。273 3.每趟快速排序的结果如下：462 87 275 61 170 503 897 908 653 512 170 87 275 61 462 61 87 170 27561 87 512 653 897 908 512 653 排序后:61 87 170 275 462 503 512 653 897 908 4.二叉排序树：(4 分）删除 72 后:（2 分)5。构造的哈夫曼树为:（4分）加权路径长度WPL=80（2 分）四、算法设计题(每小题 10 分,共 30 分）1.void ListInsert(Linklist L，int x）Linklist p，q;q=L;p=q-next；while(p&xp data)q=p；p=p next；s=（Linklist）malloc(sizeof(LNode)；s-data=x；s-next=p；q next=s；2。int BtDepth（Bitree T)int lchilddep，rchilddep;if(T）return(0）；else lchilddep=BtDepth(T lchild);rchilddep=BtDepth（T-rchild）；return(lchilddep rchilddep）？（lchilddep+1）：(rchilddep+1);3。void LayerOrder(Bitree T）InitQueue(Q);EnQueue(Q，T）;while（！QueueEmpty（Q)DeQueue（Q,p）；visit（p）；if(p lchild)EnQueue（Q，p-lchild）;if（prchild)EnQueue（Q,p rchild);
