数据结构模拟

一、 单项选择:（每空2分，共30分）

1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① C 、数据信息在计算机中的②

A 以及一组相关的运算等的课程。

① A．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ B _。

A. 正确 B. 不正确

3. 一个栈的入栈序列a，b，c，d，e，则栈的输出序列是_ A ___。 A. edcba B. decba C. dceab D. abcde 4. 栈的特点是__ B __，队列的特点是__ A __。 A. 先进先出 B. 先进后出 5．空串与空格串是相同的，这种说法_ B ___。

A. 正确 B. 不正确

6. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为_ C ___。

A. SA+141 B. SA+144 C. SA+222 D. SA+225

7. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序

为_ B ___。 A. uwvts B. vwuts C. wuvts D. wutsv

8. 深度为5的二叉树至多有__ C __个结点。

A. 16 B. 32 C. 31 D. 10

9．在一个无向图中，所有顶点的度数之和等于所有边数的__ C __倍。

A. 1/2 B. 1 C. 2 D. 4

10.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_ C ___.

A. n B. n/2 C. (n+1)/2 D. (n-1)/2

11. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为__ C __。

A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)

12. 下述几种排序方法中，要求内存量最大的是_ D ___。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

13. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素

进行比较，将其放入已排序序列的正确位置上的方法，称为_ C ___。

A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

二、填空:（每空2分, 共20分）

1. 分析下面算法（程序段），给出最大语句频度 n ，该算法的时间复杂度是_ O (n2)_

for (i=0;i

A[i][j]=0;

2. 在双向链表中，每个结点有两个指针域，一个指向____前驱结点__，另一个指向后继结点

3．空串是__ 零个字符的串 __，其长度等于_零_ __。

4．折半查找的存储结构仅限于___顺序存储结构 _，且是_有序的 ___。

5．一个图的 邻接矩阵 表示法是唯一的，而 邻接表 表示法是不唯一的。

2

三、用图表回答下列问题:（共20分）

1．设某通信系统使用八A，B ，C，D，E，F，G，H个字符，他们出现的概率w={５，

２９，７，８，１４，２３，３，１１}，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）?

2．根据下面的邻接链表，画出相应的图，并写出每个顶点的度。

v2 v1

v2 v3

v3 v4 ^ v5 v6 ^ v4 v6 v3 ^ v6 v5 v5 v4 ^ 19 D 8 H 11 100 42 F 23 48 29 B 29 E 15 C 7 G 3

A 5 8 14 解：

V1: 3 V2: 2 V3: 3 V4: 2 V5: 4

v4 v5 v1 v2 v3 V6: 2

V6 四、阅读下列算法，分析它的作用：（每小题10分，共20分） 1. 阅读下列算法，说明该算法的作用。

// 类定义 ElemTtype Sqstack::pop( )

{ ElemType x;

if ( top==0 ) x=-999; else { x = elem[top]; top--; } return x;

} // pop

const int MAX=20; typedef char ElemType ; class Sqstack { private: ElemType elem [MAX]; int top ; public: Sqstack(){top=0}; ElemType pop(); void push(ElemType x); //…….; } ;

答：该算法是顺序栈类的出栈算法。

如果栈空返回-999；否则返回出栈元素的值。

2. 有如下图所示单链表，经过reverse 算法处理后，单链表发生了什么变化 ？

画出处理后的单链表图示。

struct Snode //结点结构 void Link ::reverse()

{ char data; { Snode *p, *q ;

Snode *next ; } ; class Link //链表类 { private: Snode *Head; public: Link (){Head =NULL}; void creat(); void reverse (); void output(); //…….; p= Head ->next;

Head ->next=NULL;

while( p !=NULL) { q=p->next ;

p->next= Head ->next; Head >next=p; p=q; } } // reverse

Head a b c d e ^

答：该算法是将链表逆置的算法。 链表逆置后，具体如下图：

Head

e d c b a ^ 五、算法设计题。

1. 写一算法，统计二叉树的叶子结点的个数。

//利用中序遍历方法，或者先序、后序均可以

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构模拟在线全文阅读。