全国年月高等教育自学考试
数据结构导论试题
课程代码
一单项选择题(本大题共小题每小题分共分)
在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题后的括号内错选多选或未选均无分
数据的基本单位是（）
A数据项 B数据类型
C数据元素 D数据变量
下列程序的时间复杂度为（）
i=s=
while（s<n）
{ i++
s=s+i
}
AO（ ） BO（ ）
CO（n） DO（n）
若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素则最节省运算时间的存储方式是（）
A单链表 B仅有头指针的单循环链表
C双链表 D仅有尾指针的单循环链表
从一个长度为n的顺序表中删除第i个元素（≤i≤n）时需向前移动的元素的个数是（）
Ani Bni+
Cni Di
顺序栈S中top为栈顶指针指向栈顶元素所在的位置elem为存放栈的数组则元素e进栈操作的主要语句为（）
Aselem［top］=e Bselem［top+］=e
stop=stop+ stop=stop+
Cstop=stop+ Dstop=stop+
selem［top+］=e selem［top］=e
循环队列sq中用数组elem［&#;&#;］存放数据元素sqfront指示队头元素的前一个位置sqrear指示队尾元素的当前位置设当前sqfront为sqrear为则当前队列中的元素个数为（）
A B
C D
设有一个阶的对称矩阵A采用压缩存储方式以行序为主序存储a为第一个元素其存储地址为每个元素占有个存储地址空间则a的地址为（）
A B
C D
含有个结点的二叉树中度为的结点数为则度为的结点数为（）
A B
C D
对一棵有个结点的完全二叉树按层编号则编号为的结点它的父结点的编号为（）
A B
C D
可以惟一地转化成一棵一般树的二叉树的特点是（）
A根结点无左孩子 B根结点无右孩子
C根结点有两个孩子 D根结点没有孩子
有n个结点的有向完全图的弧数是（）
An Bn
Cn(n) Dn(n+)
设图的邻接链表如题图所示则该图的边的数目是（）
A B
C D
已知一个有序表为（）当二分检索值为的元素时检索成功需比较的次数是（）
A B
C D
排序算法中第一趟排序后任一元素都不能确定其最终位置的算法是（）
A选择排序 B快速排序
C冒泡排序 D插入排序
排序算法中不稳定的排序是（）
A直接插入排序 B冒泡排序
C堆排序 D归并排序
二填空题(本大题共小题每小题分共分)
请在每小题的空格中填上正确答案错填不填均无分
在数据结构中数据的逻辑结构分为集合________树形结构和图状结构等四类
通常从正确性易读性________和高效率等个方面评价算法（包括程序）的质量
顺序表的存储密度为________而链表的存储密度为________
对于栈只能在________插入和删除元素
在循环队列中存储空间为～n设队头指针front指向队头元素前一个空闲元素队尾指针指向队尾元素那么队满标志为front=(rear+)%n队空标志为________
三个结点可构成________种不同形态的二叉树
对于一棵具有n个结点的二叉树当进行链接存储时其二叉链表中的指针域的总数为n个其中________个用于链接孩子结点
有向图G用邻接矩阵A［&#;&#;n&#;&#;n］存储其第i列的所有元素之和等于顶点Vi的________
对二叉排序树进行________遍历可得到排好序的递增结点序列
采用折半查找方法进行查找的数据序列应为________且________
索引文件只能是________因为索引文件的组织方式是为随机存取而设计的
在插入和选择排序中若初始数据基本正序则选用________若初始数据基本反序则选用________
快速排序最好情况下的时间复杂度为________最坏情况下的时间复杂度为________<
