数据结构模拟题

2、在一份电文中共使用五种字符:A,G,F,U,Y,Z,它们的出现频率依次为12,9,18,7,14,11,求出每个字符的哈夫曼编码。

四、阅读算法,回答问题(每小题5分,共20分)

1、void AA (LNode * HL,const ElemType & item) {

LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL;

while ( p->next!=HL ) p=p->next;

newptr->next=HL; p->next=newptr; }

对于结点类型为LNode的单链表,以上算法的功能为:

2、void BB(List &L) {

int i=0;

while (i

int j=i+1;

while (j

if(L.list[j] = =L.list) {

for (int k=j+1;k

else j++; } i++; } }

以上算法的功能为:

3、void CC(BTreeNode * & BST ) {

ElemType a[6 ]={45,23,78,35,77,25}; BST=NULL; for( int i=0,i<6;i++) Insert(BST , a[i]); }

调用该算法后,生成的二叉搜索数的中序序列为:

4、void DD ( ) {

ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9);

for ( int i=0; i<10; i++) cout<

调用该算法后,输出结果为:

五、算法填空,在画有横线的地方填写合适的内容(10分)。

利用单链表进行数据排序。

void LinkSort (ElemType a[ ],int n) {

LNode * head=new LNode; InitList (head); int i;

for (i=0;inext; i=0;

while ( ) {

a[i++]=p->data; }

ClearList (head);

}

六、编写算法(10分)

编写一个非递归算法,在稀疏有序索引表中二分查找出给定值K所对应的索引项,即索引值刚好大于等于K的索引项,返回该索引项的start域的值,若查找失败则返回-1。

答案

一、单选题 (每空2分,共10分)

1、A 2、 A 3、A 4、 B 5 、A

二、填空题(每空1分,共20分)

1、顺序结构、链接结构、索引结构、散列结构 2、2i+1、2i+2、?(i-1)/2? 3、栈顶元素、栈顶指针 4、6 5、2、2、0、7

6、n(n-1)/2 、n(n-1)

7、稠密、稀疏

8、二叉搜索树、理想平衡树

三、运算题(每小题5分,共10分)

1、(64) (52,64) (12,64,52) (12,48,52,64) (12,45,52,64,48) (12,45,26,64,48,52)

2、 A:111 G:011 F:10

U:010 Y:00 Z:110 (或0、1 相反)

四、阅读算法,回答问题(每小题5分,共20分)

1、向单链表的末尾添加一个元素。 2、删除线性表中所有重复的元素。 3、23 25 35 45 77 78

4、 1 2 3 4 5 6 7 8 9 10

五、算法填空,在画有横线的地方填写合适的内容(10分)。

p!=NULL p=p->next; delete head;

六、编写算法(10分)

int Binsch(IndexList B, int m, IndexKeyType K) {

int low=0, high=m-1; while (low<= high) {

int mid=(low+high)/2; if (K= =B[mid]. index ) return B[mid].start; else if (K

low=mid+1; }

if (low

《数据结构》模拟题(三)

一、单选题 (每空2分,共10分)

1、在一个长度为n的顺序存储的线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元

素时,需要从后向前依次后移( )个元素。

A.n-i B.n-i+1 C.n-i-1 D.i

2、在线性表的散列存储中,若用m表示散列表的长度,n表示待散列存储的元素的个数,

则装填因子?等于( )。

A.n/m B.m/n C.n/(n+m) D.m/(n+m)

3、从一棵B_树删除元素的过程中,若最终引起树根结点的合并,则新树高度是( )。 A.原树高度加1 B.原树高度减1

C.原树高度 D.不确定 4、在稀疏矩阵的带行指针向量的链接存储中,每个行单链表中的结点都具有相同的( )。 A.行号 B.列号

C.元素值 D.地址

5、在一个具有n个顶点的无向图中,要连通所有顶点则至少需要( )条边。

A.n B.2n C.n-1 D.n+1

二、填空题(每空1分,共20分)

1、 对于双目操作符,其重载函数带有__________个参数,其中至少有一个为____________

的类型。

2、 从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________,输出一个二维

数组b[m][n]中所有元素值的时间复杂度为________。

3、在归并排序中,进行每趟归并的时间复杂度为________,整个排序过程的时间复杂度为

________,空间复杂度为________。

4、在一棵m阶B_树上,每个非树根结点的关键字数目最少为________个,最多为________

个,其子树数目最少为________,最多为________。

5、当从一个小根堆中删除一个元素时,需要把________元素填补到________位置,然后再

按条件把它逐层________调整。

6、快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为

________。

7、从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明_______,若

元素的值小于根结点的值,则继续向________查找,若元素的大于根结点的值,则继续向________查找。

8、在一个单链表HL 中,若要向表头插入一个由指针p指向的结点,则应执行语句:

联系客服:779662525#qq.com(#替换为@)