数据结构09

一. 填空题（26分，每空2分）

1. 声明抽象数据类型的目的是________________________________________。

2. 已知结点类Node有data和next域，下列数据存储结构声明分别为

__________________________________和_____________________________________。

3. 已知SString s1("aababbabac"),s2("aba");，执行下列语句后，s1字符串是______________。

(0,1),s2);

(0,2));

4. 中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K的后缀表达式为______________________。

5. 设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有__________个元素。

6. 已知二维数组a[10][8]采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a[4][5]的存储地址是__________________________。

7. 已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_______。

8. 中根遍历序列和后根遍历序列相反的二叉树是_________________________________。

9. 由256个权值构造一棵哈夫曼树，则该二叉树共有________________结点。

10. 由n个顶点组成的无向连通图，最多可以有_____________________条边。

11. 10个元素的排序数据序列采用折半查找的平均查找长度 是（写出算式）_____________________________________________________。

12. 已知关键字序列为{67,41,34,10,69,24,78,54,41*}，采用快速排序算法按升序排序，以第一个元素为基准值，其第一趟排序后的关键字序列为____________________________。

二. 问答题（45分，每小题5分）

1. 已知目标串为"aabcbabcaabcaababc"，模式串为"abcaababc"，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。

2. 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？

3. 已知一棵二叉树中根次序遍历序列为GCBHKAMFDJE，后根次序遍历序列为CBGHMAJEDFK，画出这棵二叉树并进行中序线索化。

4. 设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18}，采用哈夫曼编码对这段正文进行压缩存储，画出所构造的哈夫曼树，并写出每个字符的哈夫曼编码。

5. 删除以下带权无向图中的顶点D，画出删除D后图的邻接矩阵表示和邻接表表示。

6. 构造以下带权无向图的最小生成树，并给出该最小生成树的代价。

7. 已知关键字序列为{16,74,60,43,54,90,46,31,29,88,71,64,50}，散列表长度为11，采用除留余数法的散列函数为hash(k)=k % 11，画出采用链地址法构造的散列表，计算 （写出算式）。

8. 画出对关键字序列{93,17,56,42,78,15,42*,25,19}进行希尔排序（升序）的每一趟排序过程，说明希尔排序算法的稳定性并解释原因，以及希尔排序适用于什么存储结构。

9. 将关键字序列{29,10,25,26,58,12,31,18,47}用筛选法分别建成一个最大堆和一个最小堆，写出两个堆序列并画出其对应的完全二叉树。

三. 程序阅读和改错题（15分，每小题5分）

1. 阅读以下函数，回答问题。

template

void CirHDoublyLinkedList::concat(CirHDoublyLinkedList &list)

{

DLinkNode *rear=head->prev;

rear->next = >next;

>next->prev = rear;

rear=>prev;

rear->next = this->head;

this->head->prev = rear;

>prev = ;

>next = ;

}

上述函数功能是什么？以下调用语句的运行结果是什么？

CirHDoublyLinkedList source("abcdef",6), list("xyz",3);

(list);

cout<<"source："<："<

2. 下列trim()函数欲删除当前字符串对象中的所有空格字符。

void SString::trim() 已知三叉链表表示的二叉树结点类TriNode声明如下：

template

class TriNode 程序设计题（14分，每小题7分）

1. 在带头结点的单链表类HSLinkedList中，增加以下成员函数：

void HSLinkedList::removeAll(HSLinkedList &list) 求二叉树中指定结点的层次。

一. 填空题（26分，每空2分）

1. 使数据类型的定义和实现分离，使一种定义有多种实现。

2. Node*table[4]; Node table[4];

3. "abac"

4. ABCDEF+*G/-H+*+IJ+K*-

5. 36

6. 1148

7. 7

8. 右单支二叉树（包括空二叉树、只有根结点的二叉树）

9. 511

10. n*(n-1)/2

11.

12. {41* 41 34 10 54 24} 67 {78 69}

二. 问答题（45分，每小题5分）

1. 模式串"abcaababc"改进的next数组为

2. 栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。深度优先搜索遍历算法需要使用栈作为辅助结构，广度优先搜索遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。

顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。

链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。

(3)

(4)

(5)

.

(6)

，代价是45

(7)

(8)

希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。

（9）

三. 程序阅读题（15分，每小题5分）

1. 将list链表合并连接到当前链表最后，设置list链表为空

source：(a, b, c, d, e, f, x, y, z)

list：()

2. ①运行结果为“abcdefxyz e f xyz”，正确的运行结果是“abcdefxyz”。

② trim()函数首先寻找串的第一个空格字符，用i记住空格字符下标；再遍历串，将串中的非空格字符（用j记住其下标）逐个向前移动到空格字符位置（i下标）；算法存在错误，删除后没将字符串结束符'\0'向前移动到len处，导致cout输出仍然到'\0'，如下图所示。

③ 改正：函数体最后增加以下一句：

element[len] = '\0';

3. 深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下：

① 当TriNode构造函数不指定parent时

template

TriNode* TriBinaryTree::copy(TriNode *p)

{

TriNode *q=NULL;

if (p!=NULL)

{ q = new TriNode(p->data); 程序设计题（14分，每小题7分）

以下给出参考程序，阅卷老师可根据实际情况评分，重点是表达算法思想。

1. 在带头结点的单链表类HSLinkedList中，增加以下成员函数，删除所有与list匹配的子表。

template

void HSLinkedList::removeAll(HSLinkedList &list)

{ Node *start=head->next, *front=head;

while (start!=NULL)

{ Node *p=start, *q=>next;

while (p!=NULL && q!=NULL && p->data==q->data) 求二叉树中指定结点的层次。

一棵二叉树中结点所在的层次定义：令根结点的层次为1，其他结点的层次是其父母结点的层次加1。

① 在二叉链表存储的二叉树类BinaryTree中增加成员函数如下：

template

int BinaryTree::getLevel(T x) //返回x结点所在的层次

{ //若空树或未查找到x返回-1

if (root==NULL)

return -1;

return getLevel(root, 1, x); //令根结点的层次为1

}

template

int BinaryTree::getLevel(BinaryNode *p, int i, T x)

{ //在以p结点（层次为i）为根的子树中求x结点所在层次

if (p!=NULL)

{ if (p->data==x)

return i; //查找成功

int level = getLevel(p->left, i+1, x); //在左子树查找

if (level!=-1)

return level;

return getLevel(p->right, i+1, x); //继续在右子树中查找

}

return -1; //查找不成功

}

② 在二叉链表结点类BinaryNode中增加表示结点层次的成员变量level，结点构造函数声明如下：

BinaryNode(T data, BinaryNode *left=NULL, BinaryNode *right=NULL, int level=0)

构造二叉树时设置每个结点的层次属性。例如，二叉树类BinaryTree的一种构造函数声明如下：

template

BinaryTree::BinaryTree(T prelist[], int n) //以标明空子树的先根序列构造一棵二叉树

{ int i=0;

root=create(prelist, n, i, NULL, 1); //根结点的层次为1

}

//以标明空子树的先根次序遍历序列创建一棵子树，该子树根结点是prelist[i]，

//根结点层次是level，其父母结点由parent指向，返回创建子树的根结点指针

template

BinaryNode* BinaryTree::create(T prelist[], int n, int &i, int level)

{ BinaryNode *p=NULL;

if (i

{ T elem = prelist[i++];

if (elem!=NULL)

{ p = new BinaryNode(elem, NULL, NULL, level); //创建结点，层次是level

p->left = create(prelist, n, i, level+1); //创建左子树

p->right = create(prelist, n, i, level+1); //创建右子树

}

}

return p;

}

BinaryTree类的getLevel(p)成员函数声明如下，算法同查找。

template

int BinaryTree::getLevel(T x) //返回值为x结点所在的层次，若空树或未查找到x返回-1

{ BinaryNode *find=search(x); //查找

if (find==NULL)

return -1;

return find->level;

}

在二叉树中插入一个结点时，以插入结点为根的子树中所有结点的层次也随之改变，因此，BinaryTree类需要提供以下setLevel()方法动态维护层次属性。

//设置以p结点（层次为level）为根的子树中所有结点的层次

template

void BinaryTree::setLevel(BinaryNode *p, int level)

{ if (p!=NULL)

{ p->level = level;

setLevel(p->left, level+1);

setLevel(p->right, level+1);

}

}