B C

/ \\ / D E F / G

25. 图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请画出该图的最小代价支撑树，并计算最小代价支撑树的权。

图2

解答:

（每条边1分，画方框的两条边任选一条）

最小代价支撑树的权=56 （3分）

26. 设一个闭散列表具有10个桶，散列函数H（x）=x%7，若元素输入顺序为：

{50，42，85，22，76，19，34，68}，解决冲突用线性重新散列技术，要求画出构造好的散列表。

解答:（8分，第二行每个数字1分）

0 42 1 50 2 85 3 22 4 5 19 6 76 7 34 8 68 9

四、算法设计（本大题共2小题，第27小题10分，第28小题12分，共22 分） 请在答题纸相应的位置上填写正确答案。写在试卷上不得分。

27.二叉搜索树T用二叉链表存储结构表示，其中各元素的值均不相同。编写算

法，按递减顺序打印T中各元素的值。结点结构定义如下： typedef int TreeItem;

typedef struct btnode *btlink; typedef struct btnode{ TreeItem data; btlink left, right; }BTNODE; 解答:

void f(btlink t) { // 或void f(BTNODE *t) if(t){

f(t->right);

printf(\ f(t->left); } }

28. 阅读下面程序，其功能是调整线性表中的元素，将所有奇数放在表的左边，将所有偶数放在表的右边。请填空完成该程序。（每空1分，共12 分）

#define MAXSIZE 100 typedef int ElemType; typedef struct{

ElemType elem[MAXSIZE]; int last; /*末元素下标*/

}SeqList;

void AdjustSqlist(SeqList *L){

ElemType temp; int i=0, j= ⑴ ; while(i

while(L->elem[ ⑵ ]%2 != 0 && ⑶ )

i++;

while(L->elem[ ⑷ ]%2 = = 0 && ⑸ )

j--;

if( ⑹ )break;

temp = L->elem[i];

}

}

L->elem[i]= ⑺ ; L->elem[j]= ⑻ ; void main(){

SeqList ⑼ ;

int r, i; }

解答:（每空1分，共12分，大小写不能错）

⑴、_______ L->last _____________ ⑶、_______ ilast或i0或ielem[j]__________ ⑼、_______*sq _________________ ⑾、_______ r-1_________________

⑵、_______ i ______________________ ⑷、_______ j ______________________ ⑹、_______ i>=j ___________________ ⑻、______ temp __________________ ⑽、_______SeqList *_____________ ⑿、_______sq->elem[i]____________

sq=( ⑽ )malloc(sizeof(SeqList)); printf(\请输入线性表的长度:\scanf(\

sq->last = ⑾ ; printf(\请输入线性表的各元素值:\\n\

for(i=0; i<=sq->last; i++) scanf(\ ⑿ ); AdjustSqlist(sq);

08专升本数据结构考题解答

一、 单项选择题（共12小题，每小题2 分，共24分） 1．用非递归方法实现递归算法时通常要使用 A．循环队列 B．栈

C．二叉树

D．双向队列

2．对于一个具有n个顶点和e条弧的赋权有向图，如果用赋权邻接矩阵表示这个图，请问求单源最短路径的Dijkstra算法的时间复杂度为 A．O(n) B．O(n+e)

3．设语句x++的执行时间时单位时间，以下语句的时间复杂度是

for(i=1; i<=n; i++) for(j=1; j<=n; j++)

x++;

C．O(n*n*n)

D．O(n*n)

C．O(n*n)

D．O(2e)

A．O(1) B．O(n)

4．一高度为h的非空二叉树（假设只含根节点的树的高度为1）最多有几个节点 A．2h

5．赋权有向图G用用赋权邻接矩阵A存储，则节点i的入度等于 A．第i行非∞的元素之和

B．第i列非∞的元素之和 D．第i列非∞且非0的元素个数

B．2h-1

C．2h-1

D．2h

C．第i行非∞且非0的元素个数

6．设双链表的节点类型定义如下， typedef typedef

struct

node

*link;

struct node{

ListItem element; link left; link

right;

}*p,*q,*r;

删除双链表中节点p(由p指向的节点)的操作是 正确的做法如下图：