2009数据结构练习题[1]

《2009数据结构练习题[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2009数据结构练习题一、选择题（D）1、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间：A、单链表B、双链表C、单循环链表D、顺序表。（A）2、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为。A、98B、99C、50D、48（A）3、数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5,5]的地址是。A、1140B、1145C、1120D、1125（C）4、对二叉树从1开

2、始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用实现编号。A、先序遍历B、中序遍历C、后序遍历D、从根开始进行层次遍历（B）5、栈和队列都是。A、顺序存储的线性结构B、限制存取点的线性结构C、链式存储的线性结构D、限制存取点的非线性结构（C）6、若二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是。A、二叉排序树B、哈夫曼树C、堆D、AVL树（C）7、在顺序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半法查找关键码值11，所需的

3、关键码比较次数为。A、2B、3C、4D、5（C）8、一组记录的关键字为(46,79,56,38,40,84),利用快速排序的方法，以第一记录为基准得到的一次划分结果为。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,79（D）9、对包含n个元素的哈希表进行查找，平均查找长度为。A、O(log2n)B、O(n)C、O(nlog2n)D、不直接依赖于n（C）10、一个有n个顶点的无向图最多有边。A、nB、n(n-1)C、n(n-1)/2D、2n（B）1

4、1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是。A.60B.66C.18000D.33（B）12、有关二叉树下列说法正确的是。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2（C）13、二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-1（D）14、n个结点的完全有向图含有边的数目。A．n*nB．n（n＋１）C．n／2D．n*（n－l）（BD）15、一个有n个结点的图，最少有个连通分量

5、，最多有个连通分量。A．0B．1C．n-1D．n（B）16、一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定（A）17、关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路（D）18、设一个栈的输入序列是A，B，C，D，则借助一个栈所得到的输出序列不可能是。A．A，B，C，DB．D，C，B，AC．A，C，D，BD．D，A，B，C（C）19、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为。A、48B、49

6、C、50D、51二、填空题1、已知L是带表头结点的非空单链表，且P结点既不是头结点，也不是尾结点，请填写删除P结点直接后继结点的主要语句序列（可利用辅助结点变量Q）：Q=P->NEXT、P->NEXT=P->NEXT->NEXT、free(Q)。1、广义表A＝((),（a,(b,c)）,d)的表尾Gettail(A)为：(a,(b,c)),d)。2、对任意一棵二叉树，若终端结点数为n0,则度为2的结点数为:n0-1。3、在顺序表（即顺序存储结构的线性表）中插入一个元素，需要平均移动n/2元素。4、已知一棵二叉树的前序序列为ABDFCE，中序序列为

7、DFBACE，则后序序列为：FDBECA。5、通常是以算法执行所耗费的时间和所占用的空间来判断一个算法的优劣。6、已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是：A[2][3]。三、判断题：正确的在（）中填入“√”，错误的填入“×”。（×）1、线性表的逻辑顺序与物理顺序总是一致的。（×）2、线性表的顺序存储表示优于链式存储表示。（√）3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（×）4、二维数组是其数组元素为线性表的线性表。（√）5、每种数据结构都应具备三种

8、基本运算：插入、删除和搜索。（×）6、如果一个二叉树中没有度为1的结点，则必为满二叉树。（×）7、内部排序是指排序过程在内存中进行的排序