数据结构试题（含答案）(2)

E. 4 F. 5 G. 6 H. 7 30．已知某有向图的邻接表存储结构如图所示。 ? ??????? 0 E 2 1 ∧

1 D 0 3 4 ∧

2 C 4

3 B 1 2 0 ∧

4 A 2 ∧

根据存储结构，依教材中的算法其深度优先遍历次序为（ d ）。 广度优先遍历次序为（ c ）。各强连通分量的顶点集为（ ）。

a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc及ed f: ac及bed g: ab及ced h: bc及aed 31. 已知某无向图的邻接表如下所示；

( )是其原图。 ( )是按该邻接表遍历所得深度优先生成树。 ( )是按该邻接表遍历所得广度优先生成树。 0 a 3 2 1 1 b 3 0 2 c 4 3 0 3 d 5 2 1 0 4 e 5 2 5 f 4 3 A. a b B. a b C. a b

c d c d c d

e f e f e f

D. a b E. a b F. a b

d c c d c d

f e e f e f

32．若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定

的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至 表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。 顺序表的存储结构为： typedef struct{

ElemType *elem; //数据元素存储空间，0号单元作监视哨 int length; //表长度 }SSTable;

int search_seq(SSTable ST, KeyType key)

{ //在顺序表ST中顺序查找关键字等于key的数据元素。

//若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。 ST.elem[0].key=key; i=ST.length;

while(ST.elem[i].key!=key) ; if( )

{ ST.elem[i]←→ST.elem[i+1]； ； } return i; }

A. i>0 B. i>=0 C. i

Void heapadjust( heaptype & H , int s , int m ) {

rc=H.r[s];

for (j=2*s;j<=m;j*=2) {

if (j

; }//heapadjust

a: (H.r[j].key>H.r[j+1].key); b: !(rc.key< H.r[j].key); c: (H.r[j].keyH.r[j].key); e: H.r[s]=rc; f: rc=H.r[s]; g: h.r[j]=rc; h: rc=H.r[j];

三．算法设计题

1. 单链表结点的类型定义如下：

typedef struct LNode { int data;

struct LNode *next;

} LNode, *Linklist;

写一算法，Contrary(linklist &L) ,对一带头结点且仅设尾指针L的循环单链表 就地逆置。（即表头变表尾，表尾变表头。）

2．二叉树用二叉链表存储表示。

typedef struct BiTNode { TelemType data;

Struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

试编写销毁二叉树T的算法DestroyBiTree ( BiTree &T)。

3．设带头结点的单链表中的元素以值非递减有序排列，试编写算法，删除表中所有值相同的多余元素。

单链表结点的类型定义如下： typedef struct LNode{ int data;

Struct LNode *next; }LNode, *LinkList;

4．二叉树用二叉链表存储表示。

typedef struct BiTNode { TelemType data;

Struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

试编写算法，求元素值为x的结点的左孩子（返回x的左孩子的指针）。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题（含答案）(2)在线全文阅读。