(完整版)数据结构复习题(附答案)

一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。

1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域n ext。

假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n （n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。

现要求采用循环链表结构设计一个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23. 在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。

3、假设以I和0分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false （假定被判定的操作序列已存入一维数组中）。

5、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai工-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（入栈满等）给出相应的信息。

设有一个背包可以放入的物品重量为S,现有n件物品，重量分别为W, W, ...，W。

问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。

设布尔函数Knap（S，n）表示背包问题的解，W（i=1,2,... ，n）均为正整数，并已顺序存储地在数组W中。

请在下列算法的下划线处填空，使其正确求解背包问题。

Knap（S，n）若S=0则Knap—true否则若（S<0）或（S>0且n<1）则Knap—false否则若Knap（1） , =true则print（W[n]）;Knap —true否则Kn ap —Knap（2）___ ,设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4,s6, s5, si,则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。

例如:stristr2设stri和str2是分别指向两个单词的头结点, 请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。

将n(n>1)个整数存放到一维数组R中。

设计一个尽可能高效(时间、空间)的算法，将R中保存的序列循环左移p (0<p<n )个位置，即将R中的数据(x0, x i, x2,…,x n-i),变换为(X p, x p+ i, …，X n-1 ,X0 , X i,…,X p-i)。

4. 编写一个过程，对一个n x n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

7. 给定一个整数数组b[O..N-i] , b中连续的相等元素构成的子序列称为平台。

试设计算法，求出b中最长平台的长度。

【8. 给定nxm矩阵A[a..b,c..d], 并设A[i,j] < A[i,j+i](a < i < b,c < j < d-i)和A[i,j] <A[i+i,j](a w i w b-i,c < j < d).设计一算法判定X的值是否在A中，要求时间复杂度为O(m+n)。

【22.给定有m个整数的递增有序数组a[i..m]和有n个整数的递减有序数组b[i..n]，试写出算法：将数组a和b归并为递增有序数组c[l..m+n]。

(要求：算法的时间复杂度为0(m+n))4、要求二叉树按二叉链表形式存储，(i5分)(i)写一个建立二叉树的算法。

(2)写一个判别给定的二叉树是否是完全二叉树的算法。

3、已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA(i )画出这棵二叉树，并写出它的前序遍历结果；(2)将这棵二叉树转换成等价的森林或树。

24. 将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。

typedef struct node{int data ; struct node *lchild, *rchild; }bt no de;void EXCHANGE®node *bt){bt node *p, *q;if (bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q); q=(1)___; p->rchild=(2)___;⑶_=q；_____if(p->lchild) (4)一; if(p->rchild)⑸___ ; ______}} }25. 设t是给定的一棵二叉树，下面的递归程序count(t)用于求得：二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数NO。

N2、NL、NR N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;} no de;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2) __ NR++; else ⑶—; _______if(t->lchild!=NULL )(4) ; if (t->rchild!=NULL) (5) ____ ; ______}26. 树的先序非递归算法。

void example(b)btree *b;{ btree *stack[20], *p ；int top;if (b!=null){ top=1; stack[top]=b;while (top>0){ p=stack[top]; top--;printf( “ ％d' ,p->data);if (p->rchild!=nu II){( _(2) _;}if (p->lchild!=null)⑶；(4);}}}}27. 由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100typedef struct Node{char info; struct Node *lli nk, *rli nk; }TNODE;char pred[MAX],i no d[MAX];main (i nt argc,i nt **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(i no d,argv[2]);root=restore(pred,i no d,strle n( pred)); postorder(root);}TNODE *restore(char *ppos,char *ipos,i nt n){ TNODE *ptr ; char *rpos; i nt k;if(n <=0) return NULL;ptr->i nfo=(1)_for((2) _ ; rpos<ipos+n; rpos++) if(*rpos==*ppos) break;k=(3)_ _;ptr->lli nk=restore(ppos+1, (4) ______ ,k );ptr->rl in k=restore ((5) _ +k,rpos+1, n-1-k);return ptr;} postorder(TNODE*ptr) { if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf( “ %c ,ptr->info);}28. 证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

29. ① 试找出满足下列条件的二叉树1)先序序列与后序序列相同 2 )中序序列与后序序列相同3)先序序列与中序序列相同 4 )中序序列与层次遍历序列相同30. 设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTORROOTp,q,r),该算法找到p和q的最近共同祖先结点r。

31. 设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。

32. 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。

二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

分析你的算法的时、空复杂度。

33. 设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。

请编写程序，判断它们是否相似。

34. 一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。

35. 二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。

36. 设二叉树的结点结构是(Lc,data,Rc)，其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。

试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可) 。