数据结构模拟考试题

数据结构模拟考试题一

一、解答题（共30分）

1.（6分）已知一棵二叉树的后序遍历和中序遍历序列，求该二叉树的先序遍历序列。

后序遍历序列：DBGHFECA

中序遍历序列：BDACGFHE

2.（6分）设一无向图的邻接表如下：

写出从顶点J开始，分别进行“深度优先”和“广度优先”遍历的结果。

3.（8分）设有关键字集合K={18,22,44,13,20,36,25,44,35,51,41,15}采用散列存储结构，哈希表为HT[0…12]，设哈希函数H(K)=K%13，用拉链法解决冲突，构造出相应的散列表。

4.（10分）假设用于通讯的电文仅由8个字母组成，字母在中文中出现的频率分别为：7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

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

1.对于一个长度为n的顺序表，在表头插入元素的时间复杂度为( )，在表尾插入元素的时间复杂度为( )。

2. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。

3. 在以first为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为:

( )和( )。

4. 设元素A,B,C,D,E依次进栈，若要在输出端得到序列A C D B E，则应进行的操作序列为Push(S,A),Pop(S), Push(S,B),Push(S,C),( ）,（ ）, （ ），Pop(S),

Push(S,E),Pop(S)。

5. 线性结构的逻辑特征是（ ）。

6.折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。

7.任何连通图的连通分量只有一个，即是（ ）。

8.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，用希尔排序(d1=5,d2=3,d3=1)，第二趟的排序结果是（ ）。

9.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，用快速排序方法，第二趟的排序结果是（ ）。

10.数据结构的内涵包括（ ）、（ ）和（ ）

三、完善程序（共26分，每空2分）

1.以下是冒泡排序的算法，请填空完善程序。

void BubbleSort(int r[ ], int n)

{ int i,j,noswap;

int temp；

for(i=0; ;i++）

{ ;

for(j=n-2;j>=i；j--)

if( )

{ temp=R[j+1]; R[j+1]=R[j]; R[j]=temp;

noswap=0 ;

}

if( ) break；

}

}

2. 以下是顺序查找的算法，请填空完善程序：

int SeqSearch(int r[ ], int n, int k)

{

;

i=n;

while ( )

i--;

return i;

}

3. 以下是无向图基于邻接矩阵存储结构的深度优先遍历算法，从下标为v的顶点开始进行深度优先遍历，请填空完善程序：

template

void MGraph::DFSTraverse(int v)

{ cout<

;

for (j=0; j

if (arc[v][j]==1 && )

DFSTraverse( j );

}

4.以下是二叉链表为存储结构的二叉树的构造函数，“按完全二叉树层序遍历结果依次输入各结点名称，虚结点用@表示，结束用#表示”，请填空完善程序代码。

template

BiTree ::BiTree() { BiNode *s,*Q[Max];

T ch;

int front=1,rear=0;

root=NULL;

cout<<"按完全二叉树层序遍历结果依次输入各结点名称，虚结点用@表示，结束用#表示\n";

cin>>ch;

while(ch!='#')

{

s=NULL;

if( )

{ ;

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

}

;

if(rear==1) root=s;

else

{ if(s)

if( ) Q[front]->lchild=s;

else Q[front]->rchild=s;

if( ) front++;

}

cin>>ch;

}

}

四、编程题（24分）

1.（10分）链队列的类的定义如下：

template

struct Node

{ T data;

Node *next;

};

template

class LinkQueue

{ public:

LinkQueue();

~LinkQueue();

void EnQueue(T x);

T DeQueue();

T GetQueue()

{ if (front!=rear) return front->next->data;} bool Empty() { return front==rear? 1:0;}

private:

Node *front, *rear;

};

请写出其入队函数EnQueue(T x)和出队函数DeQueue()的算法代码。

2.（14分）顺序表的类定义如下：

const int MaxSize=100;

template

class SeqList

{

public:

SeqList( );

SeqList(T a[], int n);

~SeqList();

int Length();

T Get(int i);

int Locate(T x);

void Insert(int i, T x);

T Delete(int i);

void PrintList();

bool Empty();

private:

T data[MaxSize];

int length;

};

请写出其插入函数Insert(int i, T x)和删除函数Delete(int i)的算法代码。

数据结构模拟考试题二

一、解答题（共30分）

1.（6分）分别写出下图所示二叉树的前序、中序和后序序列。

2.（6分）设一无向网络的邻接矩阵如下：

0 3 5 8 0 3 0 6 4 11

A= 5 6 0 2 0

8 4 2 0 10

0 11 0 10 0

写出从顶点0开始，分别进行“深度优先”和“广度优先”遍历的结果。

3.（8分）设有关键字集合K={20,36,25,35,51,41,15, 18,22,44,13}采用散列存储结构，填充因子α=0.75，用线性探查法解决冲突，构造出相应的散列表。

4.（10分）假设用于通讯的电文仅由8个字母组成，字母在中文中出现的频率分别为：2，6，32，3，21，7，19， 10。试为这8个字母构造哈夫曼树，并求WPL。

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

1. 在一般情况下，一个算法的时间复杂度是（ ）的函数。。

2. （ ）可作为实现递归函数调用的一种数据结构。

3. 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ）。

4. 广义表((a), (((b),c)),(d))的长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。

5. 树是n（n≥0）结点的有限集合，在一棵非空树中，有（ ）个根结点，其余的结点分成m（m＞0）个（ ）的集合，每个集合都是根结点的子树。

6. 设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边；若G为有向图，则至少有（ ）条边，至多有（ ）条边。

8.已知一组记录为(55,44,41,14,29,38,26,60,37,32)，用希尔排序(d1=5,d2=3,d3=1)，第一趟的排序结果是（ ）。

9.已知一组记录为(55,44,41,14,29,38,26,60,37,32)，用快速排序方法，第二趟的排序结果是（ ）。

10. 与其他方法相比，散列查找法的特点是（ ）。

三、完善程序（共26分，每空2分）

1.以下是直接插入排序的算法，请填空完善程序。

void InsertSort (int r[ ], int n) {

for (i=2; i<=n; i++) {

;

j=i-1;

for (j=i-1; ;j--) {