全国高等教育自学考试数据结构试题.docx
- 文档编号:11161659
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:8
- 大小:38.56KB
全国高等教育自学考试数据结构试题.docx
《全国高等教育自学考试数据结构试题.docx》由会员分享,可在线阅读,更多相关《全国高等教育自学考试数据结构试题.docx(8页珍藏版)》请在冰点文库上搜索。
全国高等教育自学考试数据结构试题
全国2006年1月高等教育自学考试数据结构试题
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.根据数据元素的关键字直接计算出该元素存储地址的存储方法是( )
A.顺序存储方法 B.链式存储方法
C.索引存储方法 D.散列存储方法
2.下述程序段中语句①的频度是( )
s=0;
for(i=1;i for(j=0;j<=i;j++) ① s+=j; A.(m+1)(m-1)/2 B.m(m-1)/2 C.(m+2)(m-1)/2 D.m(m+1)/2 3.求单链表中当前结点的后继和前驱的时间复杂度分别是( ) A.O(n)和O (1) B.O (1)和O (1) C.O (1)和O(n) D.O(n)和O(n) 4.非空的单循环链表的头指针为head,尾指针为rear,则下列条件成立的是( ) A.rear->next==head B.rear->next->next==head C.head->next==rear D.head->next->next==rear 5.若允许表达式内多种括号混合嵌套,则为检查表达式中括号是否正确配对的算法,通常选用的辅助结构是( ) A.栈 B.线性表 C.队列 D.二叉排序树 6.已知主串s=″ADBADABBAAB″,模式串t=″ADAB″,则应用朴素的串匹配算法进行模式匹配过程中,无效位移的次数是( ) A.2 B.3 C.4 D.5 7.串s=″DataStructure″中长度为3的子串的数目是( ) A.9 B.11 C.12 D.14 8.假设以行优先顺序存储三维数组R[6][9][6],其中元素R[0][0][0]的地址为2100,且每个元素占4个存储单元,则存储地址为2836的元素是( ) A.R[3][3][3] B.R[3][3][4] C.R[4][3][5] D.R[4][3][4] 9.除第一层外,满二叉树中每一层结点个数是上一层结点个数的( ) A.1/2倍 B.1倍 C.2倍 D.3倍 10.对于含n个顶点和e条边的图,采用邻接矩阵表示的空间复杂度为( ) A.O(n) B.O(e) C.O(n+e) D.O(n2) 11.如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用( ) A.深度优先搜索算法 B.广度优先搜索算法 C.求最小生成树的prim算法 D.拓扑排序算法 12.快速排序在最坏情况下的时间复杂度是( ) A.O(n2log2n) B.O(n2) C.O(nlog2n) D.O(log2n) 13.能进行二分查找的线性表,必须以( ) A.顺序方式存储,且元素按关键字有序 B.链式方式存储,且元素按关键字有序 C.顺序方式存储,且元素按关键字分块有序 D.链式方式存储,且元素按关键字分块有序 14.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为( ) A.05 B.37 C.41 D.62 15.ISAM文件的周期性整理是为了空出( ) A.磁道索引 B.柱面索引 C.柱面基本区 D.柱面溢出区 二、填空题(本大题共10小题,每小题2分,共20分) 请在每小题的空格中填上正确答案。 错填、不填均无分。 16.数据类型按其值能否分解,通常可分为_________两种类型。 17.队列的修改是按_________的原则进行的。 18.两个串相等的充分必要条件是两个串的长度相等且_________。 19.数组采用顺序存储方式表示是因为通常不对数组进行_________操作。 20.用广义表的取表头head和取表尾tail的运算,从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。 21.结点数为20的二叉树可能达期的最大高度为_________。 22.带权连通图的生成树的权是该生成树上_________。 23.所谓“就地排序”,是指排序算法辅助空间的复杂度为_________的排序方法。 24.5阶B树的根结点至少含有_________个关键字。 25.索引文件中的索引表指示记录的关键字与_________之间一一对应的关系。 三、解答题(本大题共4小题,每小题5分,共20分) 26.假设以有序对 表示从双亲结点到孩子结点的一条边,若已知树中边的集合为{,,, (1)哪个结点是根结点? (2)哪些结点是叶子结点? (3)哪些结点是k的祖先? (4)哪些结点是j的兄弟? (5)树的深度是多少? (1) (2) (3) (4) (5) 27.已知有向图G的深度优先生成森林和广度优先生成森林如下。 请写出该图的深度优先遍历序列和广度优先遍历序列。 28.当将两个长度均为n的有序表A=(a1,a2,…,an)与B=(b1,b2,…,bn)(ai≠bj, 1≤i,j≤n)归并为一个有序表C=(c1,c2,…,c2n)时,所需进行的元素比较次数最少可达n,最多可达2n-1。 (1)假设有序表C=(2,4,5,6,7,9),试举出两组A与B的例子,使它们在归并过程中进行的元素比较次数分别达到最少和最多; (2)写出一般情况下,使归并所需进行的元素比较次数分别达到最少和最多时,A与B中的元素应满足的条件。 (1) (2) 29.对下列关键字序列(33,25,48,59,36,72,46,07,65,20)构造表长为19的散列表。 假设散列函数为h(key)=key%13,用开放地址法解决冲突,探查序列为d=h(key),d+12,d-12,d+22,d-22,d+32,d-32,…,等等。 (1)画出该散列表; (2)计算该散列表的装填因子α; (3)求出等概率情况下查找成功的平均查找长度ASL。 (1) (2) (3) 四、算法阅读题(本大题共4小题,每小题5分,共20分) 30.已知head为带头结点的单循环链表的头指针,链表中的数据元素依次为(a1,a2,a3,a4,…,an),A为指向空的顺序表的指针。 阅读以下程序段,并回答问题: (1)写出执行下列程序段后的顺序表A中的数据元素; (2)简要叙述该程序段的功能。 if(head->next! =head) { p=head->next; A->length=0; while(p->next! =head) { p=p->next; A->data[A->length++]=p->data; if(p->next! =head)p=p->next; } } (1) (2) 31.已知链串的存储结构描述如下: #defineNodeSize4 typedefstructNode{ chardata[NodeSize]; structNode*next; }*LinkStr; 阅读下列算法,并回答问题: (1)t1和t2的串值分别为″Chinese″和″China″时,写出f31(t1,t2)的返回值; (2)t1和t2的串值分别为″Japan″和″Japanese″时,写出f31(t1,t2)的返回值; (3)t1和t2的串值都为″string″时,写出f31(t1,t2)的返回值; (4)简述函数f31的功能。 inff31(LinkStrt1,LinkStrt2) {//串值以′′为结束符 inti; while (1){ for(i=0;i if(t1->data[i]==′′&&t2->data[i]==′′return0; if(t1->data[i]==′′))return–1; if(t2->data[i]==′′))return1; if(t1->data[i]>t2->data[i]return1; if(t1->data[i] } t1=t1->next; t2=t2->next; } } (1) (2) (3) (4) 32.设二叉树采用二叉链表存储结构,结点的数据域data为字符类型。 阅读下列算法,并回答问题: (1)对于如图所示的二叉树,写出执行函数f32的输出结果; (2)简述函数f32的功能。 voidf32(BinTreeT) {Stacks; //定义栈s BinTreep,q; if(T==NULL)return; InitStack(&s); p=T; do{ while(p){ Push(&s,p); if(p->lchild)p=p->lchild; elsep=p->rchild; } while(! StackEmpty(s)&&q=StackTop(s)&&q->rchild==p){ p=Pop(&s); printf(″%c″,p->data); } if(! StackEmpty(s)){ q=StackTop(s); p=q->rchild; } }while(! StackEmpty(S)); } (1) (2) 33.已知有向图的邻接表表示的形式说明如下: #defineMaxNum 50 //图的最大顶点数 typedefstructnode{ intadjvex; //邻接点域 structnode*next; //链指针域 }EdgeNode; //边表结点结构描述 typedefstruct{ charvertex; //顶点域 EdgeNode*firstedge; //边表头指针 }VertexNode;//顶点表结点结构描述 typedefstruct{ VertexNodeadjlist[MaxNum]; //邻接表 intn,e; //图中当前的顶点数和边数 }ALGraph;//邻接表结构描述 下列函数f33是从有向图G中删除所有以vi为弧头的有向边。 请在空缺处填入合适的内容,使其成为一个完整的算法。 voidf33(ALGraph*G,inti) {intj; EdgeNode*p,*q; for(j=0;j p=G->adjlist[j].firstedge; while( (1) { q=p; p=p->next; } if(p! =NULL){ if(p! =G->adjlist[j].firstedge)q->next=p->next; else( (2) ; free(p); G->e=( (3) ; } } } (1) (2) (3) 五、算法设计题(本大题10分) 34.在带头结点的循环链表L中,结点的数据元素为整型,且按值递增有序存放。 给定两个整数a和b,且a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 高等教育 自学考试 数据结构 试题