发布时间 : 星期三 文章自考数据结构历年试题及答案更新完毕开始阅读7e7bb987e53a580216fcfe68
} }
(1) L=(3,7,11,14,15,20,51) (2) L=(4,7,14,20,51) (3) 在顺序表L中查找数x, 找到，则删除x，
没找到，则在适当的位置插入x，插入后，L依然有序. 31. 已知图的邻接表表示的形式说明如下： #define MaxNum 50 //图的最大顶点数 typedef struct node {
int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct {
char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct {
VertexNode adjlist［MaxNum］; //邻接表
int n, e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedef enum {FALSE, TRUE} Boolean; Boolean visited［MaxNum］; void DFSForest(ALGraph *G){ int i;
for(i=0;i
void DFSTree(ALGraph *G, int i) { EdgeNode *p; visited［i］=TRUE;
p=G->adjlist［i］. firstedge; while(p!=NULL){
if(!visited［p->adjvex］){
printf(″<%c,%c>″,G->adjlist［i］. vertex, G->adjlist［p->adjvex］. vertex); ________(2) ; }
________(3) ; } }
(1) FALSE //初始化为未访问
(2) DSFTree( G, p->adjvex ); //从相邻结点往下继续深度搜索 (3) p = p->next; //下一个未访问的相邻结点 32. 阅读下列算法，并回答问题：
(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R［］,int n){ int i,t;
for (i=0;i while(){}里是把R[ i ] 和 R[ R[ i ] ] 交换; (1) L = { 0, 1, 2, 3, 4, 5, 6, 7 }; (2)5次 33. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33 (LinkList L, LinkList H［］, int m) {//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for (i=0;i H［i］= _________(1); p=L->next; while(p) { q=p->next; j=p->key%m; _________(2); H［j］=p; __________(3); } free(L); } (1) NULL //初始化 (2) p->next = H[ j ] //和下面一句完成头插法 (3) p = q; //继续遍历L 五、算法设计题(本大题10分) 34. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode; typedef BinTNode *BinTree; 若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。 (1)就后继的不同情况，简要叙述实现求后继操作的方法； (2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。 1) a)*px 有右孩子，则其右孩子为其中序序列中的后继 b)*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点， 找到，则该结点的父结点为*px的中序序列中的后继。找不到，则无后继。 2) BinTNode * fintNext( BinTNode * px ) { if( px-> rchild ) return px->rchild; //*px 有右孩子 BinTNode *q, *qp; q = px; while( qp = q->parent ){ //未回溯到根结点 if( qp->lchild == q ) return qp; //找到1)b)所述结点 q = qp; //往上回溯 } return NULL; //未找到 } 全国2006年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．根据数据元素的关键字直接计算出该元素存储地址的存储方法是（ D ） A．顺序存储方法 B．链式存储方法 C．索引存储方法 D．散列存储方法 2．下述程序段中语句①的频度是（ C ） s=0; for(i=1;i 3．求单链表中当前结点的后继和前驱的时间复杂度分别是（ C ） A．O（n）和O（1） B．O（1）和O（1） C．O（1）和O（n） D．O(n)和O（n） 4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（ A ） A．rear->next= =head B．rear->next->next= =head C．head->next= =rear D．head->next->next= =rear 5．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（A ） A．栈 B．线性表 C．队列 D．二叉排序树 6．已知主串s=″ADBADABBAAB″，模式串t=″ADAB″，则应用朴素的串匹配算法进行模式匹配过程中，无效位移的次数是（ B ） A．2 B．3 C．4 D．5 7．串s=″Data Structure″中长度为3的子串的数目是（ C ） A．9 B．11 C．12 D．14 8．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（ B ） A．R[3][3][3] B．R[3][3][4] C．R[4][3][5] D．R[4][3][4] 9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ C ） A．1/2倍 B．1倍 C．2倍 D．3倍 10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ D ） A．O（n） B．O(e) C．O(n+e) D．O(n2) 11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ） A．深度优先搜索算法 B．广度优先搜索算法 C．求最小生成树的prim算法 D．拓扑排序算法 12．快速排序在最坏情况下的时间复杂度是（ B ） A．O(n2log2n) B．O(n2) C．O(nlog2n) D．O(log2n) 13．能进行二分查找的线性表,必须以（ A ） A．顺序方式存储,且元素按关键字有序 B．链式方式存储,且元素按关键字有序 C．顺序方式存储,且元素按关键字分块有序 D．链式方式存储,且元素按关键字分块有序 14．为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（ B ） A．05 B．37 C．41 D．62 15．ISAM文件的周期性整理是为了空出（ D ） A．磁道索引 B．柱面索引