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 _____________ ⑶、_______ i ⑵、_______ 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指向的节点)的操作是 正确的做法如下图：