72.由同一关键字集合构造的各棵二叉排序树【 】 A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 73.ISAM文件和VSAM文件的区别之一是【 】 A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 74.下列描述中正确的是【 】
A.线性表的逻辑顺序与存储顺序总是一致的
B.每种数据结构都具备三个基本运算：插入、删除和查找 C.数据结构实质上包括逻辑结构和存储结构两方面的内容 D.选择合适的数据结构是解决应用问题的关键步骤 75.下面程序段的时间复杂度是【 】 I=s=0
While(s A.O(1) B.O(n) C.O(log2n) D.O(n^2) 三、计算与算法应用题： 1.已知一个图的顶点集V和边集E分别为： 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}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 第6页共22页 3.画出下列树对应的二叉树，并写出其先根遍历序列： A B C D F E G 4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。 5.试列出如下图中全部可能的拓扑排序序列。 123456 6.设某通信系统使用A，B ，C，D，E，F，G，H八个字符，他们出现的概率w={5，29，7，8，14，23，3，11}，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）。 7.给定表（119，14，22，1，66，21，83，27，56，13，10）,请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。 8.已知一个有向图的顶点集V和边集G分别为：V={a,b,c,d,e,f,g,h} E={,, 假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。 9.设散列表的长度为13，散列函数为H（h）= k，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。 0 1 2 3 4 5 6 7 8 9 10 11 12 10.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。 11.如图所示二叉树，回答下列问题。 12.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。 13.已知一组记录的排序码为（ 46 ， 79 ， 56 ， 38 ， 40 ， 80 ， 95 ， 24 ），写出对其进行快速排序的每一次划分结果。 14.一个线性表为 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），设散列表为 HT[0..12] ，散列函数为 H （ key ） = key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 15.已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ ，中序遍历的结果是 EBCDAFHIGJ ，试写出这 第7页共22页 棵二叉树的后序遍历结果。 16.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别采用线性探查法和链接法处理冲突，则计算对应的平均查找长度。 四、阅读下列算法，分析它的作用： 1.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 2.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 3.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 # include < iostream.h> # include < stdlib.h > const int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” void main 【 】 { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; 第8页共22页 –1，请写出输出结果。 } while (!stackempty (a)) cout < } 该算法的输出结果为： __________________________________________________________. 4.读下述算法，说明本算法完成什么功能。 template unknown (BinTreeNode temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } // 类定义 该算法的功能是：________________________________ const int MAX=20; 5.阅读下列算法，说明该算法的作用。 typedef char ElemType ; void Sqstack::push(ElemType x ) class Sqstack { if ( top==MAX-1 ) { private: cout<<”\\n 满！”； ElemType elem [MAX]; else { top++; int top ; elem[top]=x; public: } Sqstack(){top=0}; } // push ElemType pop(); void push(ElemType x); //…….; } ; struct Snode //结点结构 { char data; 6.有如下图所示单链表，经过output（）算法处理后， Snode *next ; 单链表发生了什么变化 ？画出处理后的单链表图示。 } ; void Link :output() class Link //链表类 { p=Head->next; { private: while( p !=NULL) Snode *Head; { cout<<”\\n data=”< 第9页共22页 b c d e ^ void output(); //…….; 7.阅读下列算法，说明该算法的作用。 int LinkList::sum【 】 { int x;NodeType *p;p=Head->next; while(p!=NULL) { x++; p=p->next; } return x; } // pop 8.读下述算法，说明本算法完成什么功能。 void Btree ::inordern( bnode *p, int &n ) { if ( p!=NULL) { inordern( p->lch, n); if ( p->lch==NULL && p->rch==NULL) n++; inordern( p->rch, n); } } // inordern 9.void AD(Lnode* & HL) { Insert(HL,30); Insert(HL,50); Delete(HL,26); Delete(HL,55); } 假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：______________________________。 10. void AI(adjmatrrix GA,int i,int n) { cout< // 类定义 for(int j=0;j const int MAX=20; if(Ga[I][j]! =0&& GA[i][j]! =MaxValue&& ! visited[j]) typedef char ElemType ; AI(GA,j,n); class Sqstack } { private: 该算法的功能为： ElemType elem [MAX]; ___________________________________。 int top ; public: 11.阅读下列算法，说明该算法的作用。 Sqstack(){top=0}; ElemTtype Sqstack::pop【 】 ElemType pop(); { ElemType x; void push(ElemType x); if ( top==0 ) x=-999; //…….; else { x = elem[top]; } ; top--; } return x; } // pop 第10页共22页