数据结构习题集 下载本文

3.请编写一个算法,判断含n个顶点和e条边的有向图中是否存在环。并分析算法的时间复杂度。(10分)

大连理工大学2003年硕士入学试题

数据结构部分(共75分)

一、回答下列问题(20分)

1.循环队列用数组A[0..m—1)存放其数据元素。设tail指向其实际的队尾,front指向其实际队首的前一个位置,则当前队列中的数据元素有多少个?如何进行队空和队满的判断? 2.设散列表的地址空间为0~10,散列函数为H(key)=key%11(%为求余函数),采用线性探查法解决冲突,并将键值序列{15,36,50,27,19,48}依次存储到散列表中,请画出相应的散列表;当查找键值48时需要比较多少次?

3.什么是m阶B-树?在什么情况下向一棵m阶B-树中插入一个关键字会产生结点分裂?在什么情况下从一棵m阶B-树中删除一个关键字会产生结点合并?

4.什么是线索二叉树?一棵二叉树的中序遍历序列为由djbaechif,前序遍历序列为abdjcefhi,请画出该二叉树的后序线索二叉树。

二、请用类C或类PASCAL语言进行算法设计,并回答相应问题。(45分)

1.设计一非递归算法采用深度优先搜索对无向图进行遍历,并对算法中的无向图的存储结构予以简单说明。

2.用链式存储结构存放一元多项式Pn(x)=P1xel+P2xe2+…+Pnxen,其中Pi是指数为ei的项的非零系数,且满足0≤e1≤e2…

3.(1){Rl,R2,?,Rn}为待排序的记录序列,请设计算法对{R1,R2,?,Rn}按关键字的非递减次序进行快速排序。

(2)若待排序的记录的关键字集合是{30,4,48,25,95,13,90,27,18),请给出采用快速排序的第一趟、第二趟排序结果。

(3)若对(2)中给出的关键字集合采用堆排序,请问初建的小根堆是什么?

(4)当给定的待排序的记录的关键字基本有序时,应采用堆排序还是快速排序?为什么? 三、算法填空(10分)

1.一棵树以孩子兄弟表示法存储,递归算法numberofleaf计算并返回根为r的树中叶子结点的个数(NULL代表空指针)。

typedef struct node{struct node *firstchild,*nextbrother;}TFNNode; int numberofleaf(TFNNode *r) { int num;

if(r==NULL) num=0; else

if(r->firstchild==NULL)

num= +numberofleaf;

21

(r->nextbrother); else ; return(num); }

2.在根结点为r的二叉排序树中,插人数据域值为x的结点,要求插入新结点后的树仍是一棵二叉排序树(NULL代表空指针)。 二叉排序树的结点结构为

typedef struct node { int key;

struct node *lc,*rc; }BiNode;

BiNode *insert(BiNode *r,int x) { BiNode *p,*q,*s;

s=(BiNode*)malloc(sizeof(BiNode)); s->key=x;

s->lc=NULL;s->rc=NULL; q=NULL;

if(r==NULL) {r=s;return(r);} p=r;

while( ) { q=p;

if( ) p=p->lc; else p=p->rc }

if(xkey) ; else ; return; }

清华大学2001年数据结构与程序设计试题 试题内容:

一、试给出下列有关并查集(mfsets)的操作序列的运算结果: union(1,2),union(3,4),union(3,5),union(1,7),union(3,6), union(8,9),union(1,8),union(3,10),union(3,11),union(3,12), union(3,13),union(14,15),union(16,0),union(14,16),union(1,3), union(1,14)。(union是合并运算,在以前的书中命名为merge) 要求:

22

(1)对于union(i,j),以i作为j的双亲;(5分)

(2)按i和j为根的树的高度实现union(i,j),高度大者为高度小者的双亲;(5分) (3)按i和j为根的树的结点个数实现union(i,j),结点个数大者为结点个数小者的双亲。(5分)

二、设在4地(A,B,C,D)之间架设有6座桥,如下图所示:

要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么?(5分)

(2)设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路。(10分)

三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数): (1)输人的n个数据全部有序;(5分) (2)输入的n个数据全部逆向有序;(5分) (3)随机地输入几个数据。(5分) 四、简单回答有关AVL树的问题。

(1)在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)?(5分)

(2)若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码?(5分)

五、一个散列表包含hashSize=13个表项,其下标从0到12,采用线性探查法解决冲突。请按以下要求,将下列关键码散列到表中。

10 100 32 45 58 126 3 29 200 400 0

(1)散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。(7分)

(2)散列函数采用先将关键码各位数字折叠相加,再用%hashSize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。(8分) 六、设一棵二叉树的结点定义为 struct BinTreeNode{

ElemType data;

BinTreeNode *leftChild,*rightChild; }

23

现采用输入广义表表示建立二叉树。具体规定如下: (1)树的根结点作为由子树构成的表的表名放在表的最前面;

(2)每个结点的左子树和右子树用逗号隔开。若仅有右子树,没有左子树,逗号不能省略。 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结果。; 例如,对于如右图所示的二叉树,其广义表表示为A(B(D,E(G,)),C(,F))

此算法的基本思路是:依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母(假定以字母作为结点的值),则表示是结点的值,应为它建立一个新的结点,并把该结点作为左子女当(k=1)或右子女(当k=2)链接到其双亲结点上。若遇到的是左括号”(”,则表明子表的开始,将A置为1;若遇到的是右括号”)”,则表明子表结束。若遇到的是逗

号”,”,则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将A置为2。

在算法中使用了一个栈s,在进入子表之前,将根结点指针进栈,以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下: MakeEmpty(s)置空栈 Push(s,p)元素p进栈 Pop(s)退栈

Top(s)存取栈顶元素的函数

下面给出了建立二叉树的算法,其中有5个语句缺失。请阅读此算法并把缺失的语句补上。(每空3分)

Void CreateBinTree(BinTreeNode *&BT,char ls) { Stacks;MakeEmpty(s); BT=NULL; //置二叉树 BinTreeNode *p; int k;

istream ins(ls); //把串ls定义为输入字符串流对象ins char ch;

ins>>ch; //从ins顺序读入一个字符 while(ch!=”#”)

{ //逐个字符处理,直到遇到?#?为止 switch(ch)

{ case?(?: (1) k=1; break; case ?)?:pop(s); break;

24

case ?,? (2) break;

default:p=new BinTreeNode; (3) p->leftChild=NULL; p->rightChfild=NULL; if(BT==NULL) (4) else if(k==1) top(s)->leftChild=p; else top(8)->rightChild=p; } (5) } }|

七、下面是一个用C编写的快速排序算法。为了避免最坏情况,取基准记录pivot采用从left,right和mid=? (1eft+right)/2?中取中间值,并交换到right位置的办法。数组a存放待排序的一组记录,数据类型为Type,left和right是待排序子区间的最左端点和最右端点。

Void quicksort(Type a&#, int lefl,int right) { Type temp; if(left

{ Type pivot=medlian3(a,left,right); int i=left,j=right-1;

for( ; ;)

{ while(i

{ temp=a[i];a[j]=a[i];a[i]=temp;

i++;j--; } else break; }

if(s[i]>pivot)

{ temp=a[i];a[i]=a[right];a[right]=temp;} quicksort(a,left,i-1); //递归排序左子区间 quicksort(a,i+1,right);//递归排序右子区间 } }

25