www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档
C.2i-1 D.2i-1
10.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )
A.p->next=p->next->next C.p=p->next->next
B.p=p->next D.p->next=p
11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( ) A.堆排序 C.直接插入排序
B.冒泡排序 D.快速排序
12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算
S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2)) 后S的结果为( ) A.″BCQR″ C.″BCDEFG″
B.″BCDEF″ D.″BCDEFEF″
13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( ) A.LL型 C.RL型
B.LR型 D.RR型
14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为( ) A.1 C.4
B.3 D.5
15.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是( ) A.堆排序 C.直接选择排序
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为___________。
i=1； while（i 17.向一个长度为n的顺序表中第i（1≤i≤n）个元素之前插入一个元素时，需向后移动___________个元素。 第 16 页 B.插入排序 D.快速排序 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 18.在循环双链表中，删除最后一个结点，其算法的时间复杂度为___________。 19.队列的插入操作在队列的___________部分进行。 20.一个栈的输入序列是1，2，3，?，n，输出序列的第一个元素是n，则第i个输出元素为___________。 21.一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，a00为第一个元素，其存储地址为1，每个元素占有1个存储地址空间，则a85的地址为___________。 22.设字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为___________。 23.在树形结构中，没有后继的结点是___________结点。 24.一棵深度为n(n>1)的满二叉树中共有___________个结点。 25.在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是___________。 26.无向完全图G采用___________存储结构较省空间。 27.在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是___________。 28.快速排序最好情况下的时间复杂度为___________。 三、应用题(本大题共5小题，每小题6分，共30分) 29.稀疏矩阵A如下，写出矩阵A的三元组表及矩阵A的转置矩阵的三元组表。 ?0 3 0 0 0 1??0 0 0 0 0 0????5 -1 0 0 0 0? ??0 0 0 0 4 0???-3 0 0 0 0 0???30.一棵二叉树的前根遍历序列为ABCDEFG，中根遍历序列为CBDAEGF，试构造出该二叉树。 31.下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。 ?? 1 12 5 10??1 ? 8 9 ?????12 8 ? ? 2? ??5 9 ? ? 4???10 ? 2 4 ????32.给定表（80，90，50，70，75，60，40，100），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 第 17 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 33.试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.试分别写出二叉树的先根遍历和中根遍历的递归算法。 35.试编写以单链表为存储结构实现直接选择排序的算法。 全国高等教育自学考试 数据结构导论标准预测试卷(一) 第一部分选择题 一、 单项选择题(在每小题的四个备选答案中有一个正确答案。请将其序号写在题干后的括号内。每小题l分，共14分) 1．数据的基本单位是 ( ) A．数据结构 B．数据元素 C．数据项 D．文件 2．在一个单链表中，若要删除p指针所指向节点的后继节点，则执行 ( ) 3．下面关于线性表的叙述中，错误的是 ( ) A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作 4．向顺序栈中压入元素时，是 ( ) A．先移动栈顶指针，后存人元素 B．先存人元素，后移动栈顶指针 第 18 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 C．无所谓谁先谁后 D．同时进行 5．在一个顺序存储的循环队列中，队首指针指向队首元素的 ( ) A．前一个位置 B．后一个位置 C．队首元素位置 D．任意位置 6．在完全二叉树中，若一个结点是叶子结点，则它没有 ( ) A．父结点 B．兄弟结点 C．左子结点和右子结点 D．左子结点、右子结点和兄弟结点 8．由3个结点可以构造出多少种不同的二叉树 ( ) A．2 B．3 C．4 D．5 9．下面关于图的论述中正确的是 ( ) A．邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用 B．任何有向图网络拓扑排序的结果是唯一的 C．有回路的图不能进行拓扑排序 D．无向连通网络的最小生成树是唯一的 10．设图G有n个顶点和e条边，进行广度优先搜索的时间复杂度至多为 ( ) 11．查找表的逻辑结构是 ( ) A．线性结构 B．树形结构 C．图状结构 D．集合 12．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用____查 第 19 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 找方法。 ( ) A．分块 B．顺序 C．二分 D．以上皆可 13．顺序文件修改操作困难，采用______的方法可降低所需代价。 ( ) A．附加文件 B．按关键字值排序 C．按记录输入先后排序D．快速存储 14．从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端，这种排序方 法为 ( ) A．插入排序 B．归并排序 C．选择排序 D．连续存储 第二部分非选择题 二、判断题(每小题2分，共20分。正确的在括号内打“对”。错误的打“错”。) 1．数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。 ( ) 2．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此 是属于同一数据对象。 ( ) 3．数组是一组相继的内存单元。 ( ) 4．栈和队列都是顺序存储的线性结构。 ( ) 5．二叉树是树的特殊情形。 ( ) 6．用一维数组存储二叉树时，总是以前序遍历存储结点。 ( ) 7．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与 图中结点个数有关，而与图的边数无关。 ( ) 8．解决冲突的方法有“拉链法”和构造后继散列地址序列。 ( ) 9．存放在磁带、磁盘上的文件，既可能是顺序文件也可以索引结构或其它结构类型的文件。 ( ) 10．对于n个记录的集合进行快速排序，所需要的附加空间数0(n)。 ( ) 三、填空题(每小题2分。共30分) 1．一个存储结构主要包括_______、_____和附加设施。 第 20 页