自考本科试卷题型 全国2013年10月高等教育自学考试数据结构试题

全国2013年10月高等教育自学考试数据结构试题  

　　一 单项选择题 ( 本大题共 小题 每小题 分 共 分 )

　　在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题干的括号内 错选 多选或未选均无分

　　 下列各式中 按增长率由小至大的顺序正确排列的是 ( )

　　A n ! n n / B n / n n logn

　　C n log n n logn n / D logn n n n

　　 若要在单链表中的结点 *p 之后插入一个结点 *s 则应执行的语句是 ( )

　　A s >next=p >next; p >next=s; B p >next=s; s >next=p >next;

　　C p >next=s >next; s >next=p; D s >next=p; p >next=s >next;

　　 若要在 O ( )的时间复杂度上实现两个循环链表头尾相接 则应对两个循环链表各设置一个指针 分别指向 ( )

　　A 各自的头结点

　　B 各自的尾结点

　　C 各自的第一个元素结点

　　D 一个表的头结点 另一个表的尾结点

　　 栈的两种常用存储结构分别为 ( )

　　A 顺序存储结构和链式存储结构 B 顺序存储结构和散列存储结构

　　C 链式存储结构和索引存储结构 D 链式存储结构和散列存储结构

　　 已知循环队列的存储空间为数组 data[ ] 且当前队列的头指针和尾指针的值分别为 和 则该队列的当前长度为 ( )

　　A B

　　C D

　　 已知在如下定义的链串结点中 每个字符占 个字节 指针占 个字节 则该链串的存储密度为

　　typedef struct node {

　　char data[ ];

　　struct node *next;

　　} LinkStrNode;

　　A / B /

　　C / D /

　　 应用简单的匹配算法对主串 s= ″ BDBABDABDAB ″与子串 t= ″ BDA ″进行模式匹配 在匹配成功时 进行的字符比较总次数为 ( )

　　A B

　　C D

　　 二维数组 A[ ][ ] 采用列优先的存储方法 若每个元素占 个存储单元 且第 个元素的首地址为 则元素 A[ ][ ] 的存储地址为 ( )

　　A B

　　C D

　　 对广义表 L=((a b) c d) 进行操作 tail(head(L)) 的结果是 ( )

　　A ( c d ) B (d)

　　C b D (b)

　　 已知一棵树的前序序列为 ABCDEF 后序序列为 CEDFBA 则对该树进行层次遍历得到的序列为 ( )

　　A ABCDEF B ABCEFD

　　C ABFCDE D ABCDFE

　　 一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为存储结构 则计算该有向图中某个顶点出度的时间复杂度为 ( )

　　A O(n) B O(e)

　　C O(n+e) D O(n )

　　 在关键字序列 ( ) 中二分查找关键字为 和 的结点时 所需进行的比较次数分别为 ( )

　　A B

　　C D

　　 下列排序方法中 最好与最坏时间复杂度不相同的排序方法是 ( )

　　A 冒泡排序 B 直接选择排序

　　C 堆排序 D 归并排序

　　 已知含 个结点的二叉排序树是一棵完全二叉树 则该二叉排序树在等概率情况下查找成功的平均查找长度等于 ( )

　　A B

　　C D

　　 在下列各种文件中 不能进行顺序查找的文件是 ( )

　　A 顺序文件 B 索引文件

　　C 散列文件 D 多重表文件

　　二 填空题 ( 本大题共 小题 每小题 分 共 分 )

　　 抽象数据类型是指数据逻辑结构及与之相关的 ___________

　　 已知在结点个数大于 的单循环链表中 指针 p 指向表中某个结点 则下列程序段执行结束时 指针 q 指向结点 *p 的 ___________ 结点

　　q=p;

　　while(q >next!=p)q=q >next;

　　 假设 S 和 X 分别表示进栈和出栈操作 由输入序列 ABC 得到输出序列 BCA 的操作序列为 SSXSXX 则由 a*b+c/d 得到 ab*cd/+ 的操作序列为 ___________

　　 在文本编辑程序中查找某一特定单词在文本中出现的位置 可以利用串的 ___________ 运算

　　 假设以行优先顺序将一个 n 阶的 对角矩阵压缩存储到一维数组 Q 中 则数组 Q 的大小至少为 ___________

　　 在含 个结点的完全二叉树中 叶子结点的个数为 ___________

　　 在无向图中 若从顶点 a 到顶点 b 存在 ___________ 则称 a 与 b 之间是连通的

　　 如果排序过程不改变 ___________ 之间的相对次序 则称该排序方法是稳定的

　　 索引顺序查找适宜对 ___________ 的顺序表进行查找

　　 文件的检索操作可按检索条件不同分为下列四种询问 它们是简单询问 范围询问 函数询问及 ___________

　　三 解答题 ( 本大题共 小题 每小题 分 共 分 )

　　 画出下图所示二叉树的中序线索链表的存储表示

　　 已知图 G= ( V E ) 其中

　　V={a b c d e}

　　E={(a b) (b d) (c b) (c d) (d e) (e a) (e c)}

　　( )画出图 G ;

　　( )画出图 G 的邻接表

　　( )

　　( )

　　 已知自顶向下的二路归并排序的算法如下所示 按此算法对关键字序列( )进行排序 列出算法执行过程中前 次调用 Merge 函数进行归并之后的关键字序列

　　void MergeSorDC(SeqList R int low int high)

　　{// 用分治法对 R[low high] 进行二路归并排序 }

　　int mid;

　　if (low ){>

　　mid=(low+high)/2; // 分解

　　MergeSortDC(R, low, mid); // 递归地对 R[low..mid] 排序

　　MergeSortDC(R,mid+1,high); // 递归地对 R[mid+1..high] 排序

　　Merge(R, low, mid, high); // 组合，将两个有序区归并为一个有序区

　　}

　　} //MergeSortDC

　　29 .由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。Tw.WiNgWiT.CoM请画出 4 棵含 1 ， 2 ， 3 ， 4 ， 5 ， 6 六个元素且以 1 为根、深度为 4 的二叉排序树。

　　四、算法阅读题 ( 本大题共 4 小题，每小题 5 分，共 20 分 )

　　30 . L 为一个带头结点的循环链表。函数 f30 的功能是删除 L 中数据域 data 的值大于 c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。

　　LinkList f30(LinkList L, int c)

　　{

　　LinkList Lc,p,pre;

　　pre=L;

　　p= (1) ;

　　Lc=(LinkList) malloc(sizeof(ListNode));

　　Lc->next=Lc;

　　while(p!=L)

　　if(p->data>c)

　　{

　　pre->next=p->next;

　　(2) ;

　　Lc->next=p;

　　p=pre->next;

　　}

　　else

　　{

　　pre=p;

　　(3) ;

　　}

　　return Lc;

　　}

　　(1)

　　(2)

　　(3)

　　31 . 设栈 S=(1,2,3,4,5,6,7), 其中 7 为栈顶元素。

　　( 1 )写出调用 f31(&S) 后的 S ;

　　( 2 )简述函数 f31 中第 1 个循环语句的功能。

　　void f31 (Stack *S)

　　{

　　Queue Q;

　　Stack T;

　　int i=0;

　　InitQueue(&Q);

　　InitStack(&T);

　　while(!StackEmpty(S))

　　if ((i=!t)!=0) Push(&T,Pop(S));

　　else EnQueue(&Q, Pop(S));

　　while(!StackEmpty(&T))

　　Push(S,PoP(&T));

　　while(!QieueEmpty(&Q))

　　Push(S,DeQueue(&Q));

　　}

　　(1)

　　(2)

　　32 .图的邻接矩阵表示描述如下：

　　#define MaxNum 20 // 图的最大顶点数

　　typedef struct {

　　char vexs[MaxNum]; // 字符类型的顶点表

　　int edges[MaxNum][MaxNum]; // 邻接矩阵

　　int n, e; // 图的顶点数和边数

　　} MGraph; // 图的邻接矩阵结构描述

　　阅读下列算法，并回答问题：

　　( 1 )对于下列图 G 的邻接矩阵，写出函数调用 f32(&G,3) 的返回值;

　　( 2 )简述函数 f32 的功能;

　　( 3 )写出函数 f32 的时间复杂度。

　　int f32(MGraph *G, int i)

　　{

　　int d=0,j;

　　for(j=0;j n;j++)

　　{

　　if (G->edges[i][j]) d++;