2007-2010自学考试数据结构导论试题汇编

1全国2007年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．关于栈和队列的说法中正确的是（）A．栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构2．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A．线性结构B.树形结构C.线性结构和树型结构D.线性结构和图状结构4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A．q→next=s；p→next=s；B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→next=q；5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)6．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A．a，b，c，dB.a，b，d，cC.d，c，b，aD.c，d，a，b7．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列28．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A．front==rearB.(front+1)%m==rearC.rear+1==frontD.(rear+1)%m==front9．设有二维数组A［n］［n］表示如下：653421，则A［i］［i］（0≤i≤n-1）的值为（）A．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i2/210．高度为h的完全二叉树中，结点数最多为（）A．2h-1B.2h+1C.2h-1D.2h11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A．mnB.mn-1C.n(m-1)D.m(n-1)12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．nB.n-1C.n+1D.2(n-1)13．关于无向图的邻接矩阵的说法中正确的是（）A．矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等14．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A．1B.2Ｃ．3D.415．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）A．36，44，49，55，81，88B.44，36，49，55，81，88C.44，36，49，81，55，88D.44，36，49，55，88，813二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_______。17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。18．在顺序表上读表元算法的时间复杂度为_______。19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;_______;20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66L，则元素A［j］［i］的存储位置为_______。21．有4个结点且深度为4的二叉树的形态共有_______种。22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。24．一个具有10个顶点的完全无向图中有_______条边。25．一棵平衡二叉树中任一结点的平衡因子只可能是_______。26．二分查找的时间复杂度为_______。27．二路归并排序算法的时间复杂度为_______。28．文件的基本存取单位是_______。三、应用题(本大题共5小题，每小题6分，共30分)29．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。31．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出整个冒泡排序的每一趟过程。32．题32图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。4题32图33．已知连通网的邻接矩阵A=42104962812981106121，试画出它所表示的连通网并画出该连通网的最小生成树。四、算法设计题(本大题共2小题，每小题7分，共14分)34．设单链表的结点结构如下：structnode{datatypedata;structnode*next;}试编写一个函数intcount(structnode*head,datatypex)统计单链表中数据域为x的结点个数。35．试写出直接插入排序算法。全国2007年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.在数据结构中，从逻辑上可以把数据结构分成()A.线性结构和非线性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构2.for（i=0；im；i++）for（j=0；jn；j++）A［i］［j］=i*j；上面算法的时间复杂度为()5A.O(m2)B.O(n2)C.O(m×n)D.O(m+n）3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为()A.5B.6C.7D.94.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是()A.p→llinkB.p→rlinkC.p→llink→llinkD.p→llink→rlink5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是()A.110B.108C.100D.1206.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是()A.DCBAB.CDABC.DBACD.DCAB7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为()A.top++B.top--C.top不变D.top=08.除根结点外，树上每个结点()A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲9.题9图中树的度为()A.2B.3C.5D.8题9图10.有4个顶点的无向完全图的边数为()A.6B.12C.16D.2011.设图的邻接矩阵为010100110，则该图为()6A.有向图B.无向图C.强连通图D.完全图12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于()A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是()A.线性探测法B.除留余数法C.平方取中法D.折叠法14.排序算法中，第一趟排序后，任一元素都不能．．．确定其最终位置的算法是()A.选择排序B.插入排序C.冒泡排序D.快速排序15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为()A.希尔排序B.归并排序C.插入排序D.选择排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为__________型运算。17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__________”。18.单链表中逻辑上相邻的两个元素在物理位置上__________相邻。19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是__________。20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。7题21图22.具有n个顶点的连通图至少需有__________条边。23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是__________存取、直接存取和按关键字存取。27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行__________趟才能够完成。28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为__________。三、应用题(本大题共5小题，每小题6分，共30分)29.分别写出题29图中二叉树的先根、中根、后根遍历序列。8题29图30.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。题31图32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。题32图33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。四、算法设计题(本大题共