山东省专升本《数据结构》答案

《数据结构》模拟题

2010年7月

一、单选题 （每空2分，共10分）

1、队列的删除操作是在（ A ）进行。

A．队首 B．队尾 C．队前 D．对后

2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ A ）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N;

3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。

A．51 B．23 C．53 D．74

4、在一棵二叉树中，第4层上的结点数最多为（ B ）。

A．31 B．8 C.15 D．16

5、 向堆中插入一个元素的时间复杂度为（ A ）。

A．O(log2n) B．O(n) C．O(1) D． O(nlog2n)

二、填空题（每空1分，共20分）

1、数据的逻辑结构被分为顺序结构、链接结构、索引结构和散列结构四种。

2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a[1]中，其余类推，则a[i]元素的左孩子元素为2i+1，右孩子元素为2i+2，双亲元素(i>0)为(i-1)/2。

3、从一个栈删除元素时，首先取出栈顶元素，然后再前移一位栈顶指针。

4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为6 。

5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为2、2、0和7个。

6、在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。

7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为稠密索引，若对应主表中的若干条记录，则称此索引为稀疏索引。

8、对于二分查找所对应的判定树，它既是一棵二叉搜索树，又是一棵理想平衡树。

三、运算题（每小题5分，共10分）

1、 1、 空堆开始依次向堆中插入线性表（64,52, 12,48,45,26）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。（为小根堆）

（64）

（52，64）

（12，64，52）

（12，48，52，64）

（12，45，52，64，48）

（12，45，26，64，48，52）

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

A：111 G：011 F：10 U：010 Y：00 Z：110（或0、1 相反）

四、阅读算法，回答问题（每小题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[i])

{

for (int k=j+1;kL.list[k-1]=L.list[k];

L.size--;

}

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]);

}

调用该算法后，生成的二叉搜索数的中序序列为：23 4、void DD ( )

{

25 35 45 77 78

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<cout<}

调用该算法后，输出结果为： 1 2 3 4 5 6 五、算法填空，在画有横线的地方填写合适的内容(10分)。

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

void LinkSort (ElemType a[ ],int n)

{

LNode * head=new LNode;

InitList (head);

7 8 9 10

int i;

for (i=0;iInsert(head, a[i]);

LNode * p=head->next;

i=0;

while ( p!=NULL)

{

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

p=p->next;

}

ClearList (head);

delete head;

}

六、编写算法(10分)

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

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 (Khigh=mid-1;

else

low=mid+1;

}

if (lowelse return –1;

}