数据结构考题.app.doc

数据结构补考必过
41.如下函数实现中序遍历的非递归算法。请在程序处填入合适的内容，使其成为完整的算法
typedef struct node {
char data;
struct node*Ichild, *rchild; ∥左右孩子指针
} *BinTree；
void inorder( (1) )
{
InitStack(S); ∥ 初始化一个堆栈 S
while (T ||!StackEmpty(S))
{ while ( (2) )
{
Push(S,T);
(3) ;
}
if ( (4) )
{
(5) ;
printf(“%c”,T>data);
T=T>rchild;
}
}
}
快速排序算法。
fastsort(int a［］，int s，int t)
{ int i，j,temp；
i=s；
j=t；
if(s<t)
{
while（ (1) ）
{
while (a［j］<a[i])
j= (2) ；
temp=a［j］；
a［j］=a［i］；
a［i］= temp；
i=i+1;
if(i>=j) break；
while (a［i］<=a[j])
i= (3) ；
if(i>=j) break；
temp=a［j］；
a［j］=a［i］；
a［i］= temp；
j=j-1；
}
fastsort(a，s， (4) );
fastsort(a， (5) ，t);
}
}
 假设一元多项式非零项结构定义如下
typedef struct node
{ int coef,exp;// coef表示该项系数，exp 该项指数
struct node *next;
}PNode;
如下函数实现两个一元n次多项式相加操作，请完成程序。
void PADD(PNode *Pa, PNode *Pb, SequenceList *Pc)
// 已知单链表Pa和Pb中的元素按指数递增排列。求Pa和Pb和Pc
{
PNode *pa，*pb，*pc;
pa=Pa->next;//pa指向Pa第一个结点
pb=Pb->next; //pb指向Pb第一个结点
pc=Pa; //pc指向Pa头结点，也就是新元素的插入位置
while ( (1) )
{
if (pa->exp<pb->exp) //pa结点的指数<pb结点的指数，将pa插入到pc之后，pa后移
{
(2) ;
pc=pa;
pa=pa->next;
}
else
{
if（pa->exp>pb->exp）//pa结点的指数>pb结点的指数，将pb插入到pc之后，pb后移
{
pc->next=pb;
(3) ;
pb=pb->next;
}
else//pa结点的值等于pb结点的值，计算系数和
{
pa->coef=pa->coef+pb->coef;
if(pa->coef!=0) //如果系数和不等于0，pa和pb均后移
{
pc->next=pa;
pc=pa;
pa=pa->next;
pb=pb->next;
}
else//如果系数和等于0删除pa，pb向后移
{
pc=pa->next;
pa=pc;
pb=pb->next;
}

}
}
}
if( (4) ) //如果pa=null，说明Pa没有元素，将Pb的所有后继元素插入到pc之后
{
pc->next=pb;
}
else//如果pb=null，说明Pb集合没有元素，将Pa的所有后继元素插入到pc之后
{
(5) ;
}
}
44．在如图所示的的［0..M-l］的向量空间中建立两个栈stackl和stack2，最多有M个元素入栈到两个堆栈中，若stackl的栈顶指针为stackl.topl,stack2的栈顶指针为stack2.top，请回答如下问题：

(1)给出stackl的出栈算法（2分）

(2)写出stack2的入栈算法（3分）

45.某个公司关系系统中需要用移动电话作为关键字进行员工的查找，现在公司只有80名员工，数据存储空间为100个存储空间，为了快速查找需要用到哈希查找，请给出哈希函数的构建方法，和线性探测序列的开放定址法冲突的解决的函数。

46.写出用prim算法求如下图从顶点V1出发的最小生成树的算法和每步求解结果。

47．设顺序表为（13，38，27，50，76，65，49，97），请给出由大到小排序时的初始堆和前三趟排序后堆的结构。

16. AOV网是一种（ ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
17．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )
A．e B．2e C．n2－e D．n2－2e
18．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )
A.G中有弧<Vi，Vj> B.G中有一条从Vi到Vj的路径
C.G中没有弧<Vi，Vj> D.G中有一条从Vj到Vi的路径
19．有n个顶点的有向完全图的弧数为( )
A.n2 B.2n C.n（n-1） D.2n（n+1）

20．为便于判别有向图中是否存在回路，可借助于( )
A.广度优先搜索算法 B.最小生成树算法
C.最短路径算法 D.拓扑排序算法
21．连通网的最小生成树是其所有生成树中( )
A.顶点集最小的生成树 B.边集最小的生成树
C.顶点权值之和最小的生成树 D.边的权值之和最小的生成树
22．在一个长度为n的顺序表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
23. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
24．顺序查找法与折半查找法对存储结构的要求是( )
A.顺序查找与折半查找均只适用于顺序表
B.顺序查找与折半查找既适用于顺序表，也适用于链表
C.顺序查找只适用于顺序表
D.折半查找只适用于顺序表
25．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序（由小到大）的结果为（ ）。
A. 2，3，5，8，6 B. 3，2，5，8，6
C. 3，2，5，6，8 D. 2，3，6，5，8
26．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序（由小到大）结束后前4条记录关键字为（ ）。
A. 40，50，20，95 B. 15，40，60，20
C. 15，20，40，45 D. 45，40，15，20

5