北方工业大学数据结构期末温习题

1、1.如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K)(int low=0;int high=n-1;while (low=high)(int mid=if (K=Amid.key) return mid;ey);int Prime(int n)(int i=1;int x=(int) sqrt(n); while (+ix) return 1;else return 0; (1)指出该算法的功能；(2)该算法的时刻复杂度是多少？2.(1)判定n是不是是素数(或质数)(2) O (八)3.已知一个图的极点集 V 和边集 E

2、别离为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6, 7)25.用克鲁斯卡尔(Kruskal)算法和prim算法取得最小生成树，试写出在最 小生成树中依次取得的各条边。3.用克鲁斯卡尔算法取得的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20LinkList mynote(LinkList L) (D查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)

3、返回的线性表为(a2,a3,an,ai)void ABC(BTNode * BT)if BT ABC (BT-left);ABC (BT-right); coutdatalchild);If (!T lchild)&(!T rchild) s=(ListNode*)malloc(sizeof(ListNode); s data=T data;s next=Leafhead ; Leafhead=s; Inorder(T rchild);关于如下所示的二叉树(1)画出执行上述算法后所成立的结构;(2)说明该算法的功能。6. (1)LeafheadF*(2)中序遍历二叉树，按遍历序列中叶子结点数据

4、域的值构建一个以Leafhead为头指针的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表)。7.已知一个无向图的极点集为a, b, c, d, e，其邻接矩阵如下所示a b c d e0100110010000110110110110(1)画出该图的图形；(2)依照邻接矩B$从极点 a动身进行深度优先遍历和广度优先遍历，写出相应的遍历序列。7.该图的图形为:深度优先遍历序列为：abdce 广度优先遍历序列为：abedc8.已知一个散列表如以下图所示:35203348590123456789101112其散列函数为h(key)=key%13,处置冲突的方式为双重散列法，探查序列为：h

5、i=(h(key)+ i*h1(key)%m i =0,1，m 1其中h1(key)=key%11+1回答以下问题：(1)对表中关键字 35, 20, 33和48进行查找时，所需进行的比较次数各为多少?(2)该散列表在等概率查找时查找成功的平均查找长度为多少？8. (1)对关键字 3五、20、33和48进行查找的比较次数为3、2、1、1;(2 )平均查找长度 ASL3 2 1129559.以下算法的功能是比较两个链串的大小，其返回值为: TOC o 1-5 h z 1当 S|0comstr(si,S2)=0当 &当 S10请在空白处填入适当的内容。int comstr(LinkString s

6、1,LinkString s2) 面程序段的时刻复杂度是(D )for(i=0;In;i+)for(j=1;jnext;next=p-next-next;next=p;=p-next-next;.在头指针为head且表长大于 1的单循环链表中，指针 p指向表中某个结点，假设p-next-next= head,贝心 D ) 指向头结点指向尾结点C.*p的直接后继是头结点D.*P的直接后继是尾结点 TOC o 1-5 h z . 一棵含18个结点的二叉树白高度至少为(C ).4C.已知二叉树的先序序列为ABDECF ,中序序列为DBEAFC ,那么后序序列为(D ).无向图中一个极点的度是指图中(

7、B )A.通过该极点的简单途径数B.与该极点相邻接的极点数10.已知一个图如下所示，从极点C.通过该极点的回路数D.与该极点连通的极点数a动身进行广度优先遍历可能取得的序列为(C )c e f b d c b d f ec b d e f c d b f e.数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于运算.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，那么指向头结点的指针 head可用 p表示为 head=。.栈顶的位置是随着 操作而转变的。.在串S= structure中，以t为首字符的子串有 个。22.已知一个图的广度优先生成树如右图所示，那么与此相 应的广度

8、优先遍历序列为 。16.存储（或存储结构）18.进栈和退栈22. abefcdg next next19. 1224. 272时所需进行的关键字24.在有序表（12, 24, 36, 48, 60, 72, 84）中二分查找关键字 比较次数为。10.阅读以下函数 arrange。int arrange(int a,int 1,int h,int x)1 )该函数的功能是：调整整数数组a中的元素并返回分界值i,使所有v x的元素均落在a1.i上，使所有x的元素均落在 ai + 1.h上。 TOC o 1-5 h z (2) int f(int b,int n) 或 int f(int b,int

9、 n) int p,q ;int p,q ;p=arrange(b,0,n 1,0);p=arrange(b,0,n1,1);q= arrange(b,p+1,n 1,1); q= arrange(b,0,p,0); return q p;return p q; HYPERLINK l bookmark21 o Current Document 34, 5,（要求树中.假设通信电文利用的字符集为a,b,c,d,e,f），名字符在电文中显现的频度别离为:, 23, 8, 18,试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树 左小孩结点的权值小于右小孩结点的权值），然后别离写出每一个字符

10、对应的编码。对应哈夫曼褊码,3： 111010100出01c: 1011f: 00 TOC o 1-5 h z 13 .希尔排序的增量序列必需是()A.递增的B .随机的C.递减的D.非递减的11.在一个带权连通图 G中，权值最小的边必然包括在G的()A.最小生成树中 B .深度优先生成树中C.广度优先生成树中D.深度优先生成丛林中.以下程序段的时刻复杂度为_O(M2)_product= 1;for (i= n;i0;i-)for (j = i+1; j next =p - next - next的作用是。删除*P的直接后继结点.假设元素只能按 a,b,c,d的顺序依次进栈，且取得的出栈序列中

11、的第一个元素为c,那么可能取得的出栈序列为 ,不可能取得的出栈序列为 1)cbad,cbda,cdba2)cabd,cadb,cdab12 .设栈S1的入栈序列为1 2 3 4 （每一个数字为 13个元素），那么不可能取得出栈序列 3 142。但可通过增设栈 S2来实现。例如，按以下图中的箭头指示，依次通过栈S1和S2,即可取得序列3 14 2。若是用H1和H2别离表示栈S1和S2的进栈操作，用P1和P2别离表示两个栈的出栈操作，那么取彳导3 14 2的一个操作步骤为H1, H1 , H1, P1, H2, P2, P1, H2, P1, H2, P2, H1, P1, H2, P2, P2请

12、仿照上例写出利用两个栈从1 2 3 4取彳导4 1 3 2的操作步骤。H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P230 .以下函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在 Lb表中存在而La表中不存在的结点插入到La中,其中La和Lb别离为两个链表的头指针。请在空缺处填入适合内容，使其成为一个完整的算法。void union (LinkList La, LinkList Lb) (知整形数组 L 1.8中的元素依次为(9, 8, 5, 7, 6, 3, 2, 1),阅读以下函

13、数，并写出执 行函数挪用 sort(L, 8)时，对L进行的头两趟(pass别离为0和1)处置结果。Void sort (int R口,int n) (int pass = 0, k, exchange, x; do k=pass%2+1;exchange = 0; while (kRk+1) x = Rk; Rk = Rk+1; Rk+1 = x; exchange =1; K+=2 pass +;while (exchange = = 1| pass =1); 第一趟(pass = 0) : 8 9 5 7 3 6 1 2第二趟(pass = 1) : 8 5 9 3 7 1 6 212.

14、对关键字序列(56, 23 , 78, 92, 88, 67, 19, 34)进行增量为3的一趟希尔排序的结果为 TOC o 1-5 h z ()A.(19, 23, 56,34, 78, 67,88, 92)B.(23, 56,78, 66 , 88,92 ,19 34)C.(19, 23, 34,56, 67, 78,88, 92)D.(19, 23,67, 56 , 34,78 ,92 88)30.阅读以下算法，并回答下列问题：设顺序表L=(3,7,11,14,20,51),写出执行f30(&L,15)以后的L;设顺序表L=(4,7,10,14,20,51),写出执行f30(&L,10)以后的L;(3)简述算法的功能。void f30(SeqList*L, DataType x) ( int i =0, j; while (ilength & xL-data i )i+; if(ilength & x=L-data i)31. 已知图的邻接表表示的形式说明如下： #define MaxNum 50firstedge;while(p!=NULL)if(!visited p-adjvex )printf( ,G -adjlist i . vertex,G-adjlist p-adjvex . vertex); ； FALSE /初始化为未访问