全国月高等教育自学考试数据结构考试代码VIP免费

1/6全国2005年1月高等教育自学考试数据结构试题课程代码：02331第一部分选择题(共30分)一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据元素及其关系在计算机存储器内的表示，称为数据的()A.逻辑结构B.存储结构C.线性结构D.非线性结构2.某带头结点的单链表的头指针为head，判定该链表为非空的条件是()A.head==NULLB.head->next==NULLC.head!=NULLD.head->next!=NULL3.导致栈上溢的操作是()A.栈满时执行的出栈B.栈满时执行的入栈C.栈空时执行的出栈D.栈空时执行的入栈4.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是()A.(rear-front)%m==1B.front==rearC.(rear-front)%m==m-1D.front==(rear+1)%m5.假设S=″IAMASTUDENT″，则运算substr(S,4,8)的结果为()A.″MAS″B.″MASTUD″C.″ASTUDEN″D.″STUD″6.在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为()A.模式串的最末字符B.主串的第一个字符C.模式串的第一个字符D.主串的最末字符7.从广义表L=(((d),c,d))中分解得到(d)的操作为()A.head(head(head(L)))B.head(tail(head(L)))C.tail(head(head(L)))D.tail(tail(head(L)))8.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在()A.BT[i/2]B.BT[2*i-1]C.BT[2*i]D.BT[2*i+1]2/69.右图所示二叉树的中序序列是()A.DHEBAFIJCGB.DHEBAFJICGC.DBHEAFCJIGD.DBHEAFJICG10.连通图是指图中任意两个顶点之间()A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图11.下图所示带权无向图的最小生成树的权为()A.14B.15C.17D.1812.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为()A.123，145，298，314，486，508B.508，314，123，145，486，298C.486，314，123，145，508，298D.298，123，508，486，145，31413.在待排关键字序列基本有序的前提下，效率最高的排序方法是()A.直接插入排序B.快速排序C.直接选择排序D.归并排序14.在下列各棵二叉树中，二叉排序树是()15.采用ISAM或VSAM组织的文件是()A.索引非顺序文件B.顺序文件C.索引顺序文件D.散列文件3/6第二部分非选择题(共70分)二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为______。17.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。18.如果入栈序列是1，3，5，,，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。19.已知广义表LS为空表，则其深度为______。20.假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是______。21.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为______。22.在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含______条边。23.对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行______次关键字之间的比较。24.对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于______。25.将有序表中n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是______。三、解答题(本大题共4小题，每小题5分，共20分)26.(1)写出右侧图形表示的广义表L。(2)画出其表头与表尾均为(a,(b,c))的广义表L1的图形表。(1)(2)27.试推导一棵满k叉树上的叶子结点数a与非叶子结点数b之间满足以下关系：a=(k-1)b+128.假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。29.已知关键...