数据结构以前的试题..doc

一、选择题（共10题，2分/题，共20分） （下列各题有A、B、C、D四个选项,请选择一个最佳选项填入下表） 1 2 3 4 5 6 7 8 9 10 1．以下数据结构中哪一个是非线性结构？( ) A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树 2．对于二维数组A6×8采用以行序为主序的结构进行存储，每个元素需要1个字节的存储空间，且A在内存中的存储基地址为1000，则A[3][4]在内存的存储地址为：( ) A. 1019 B. 1020 C. 1027 D. 1028 3．在一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1，无度为1的结点，则度为0的结点个数为( ) A．4 B．5 C．6 D．7 4．有64个结点的完全二叉树的深度为( )(根的层次为1)。 A. 8 B. 7 C. 6 D. 5 5．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 6.下列编码中属前缀码的是(????? )。 A.{1,01,000,001}???????? B.{1,01,011,010} C.{0,10,110,11}? ? D.{0,1,00,11} 7．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为（ ）。 A. 1,2,3 B. 9,5,2,3 C.9,5,3 D.9,4,2,3 8．任何一个无向连通图的最小生成树（ ）。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 9．设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 10．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4 二、判断题（共10题，1分/题，共10分） （判断下列各题是否正确，正确的在表格相应位置内打“√”，错的打“×”） 1 2 3 4 5 6 7 8 9 10 顺序表的长度是指顺序表所占用的存储空间的大小。 在线性结构中，每个结点都有一个直接前驱和一个直接后继。 若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二又树。 压缩关键路径上的活动的工期，一定可以缩短整个工程的工期。 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 队列的操作遵循FIFO的原则，栈则遵循LIFO原则。 在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O（n）。 空格串和空串是一样的。 Prim算法适用于求边稠密的网的最小生成树。 对于哈希表，若在采用线性探测法处理冲突，则所有同义词在表中相邻。 三、填空题（共10题，2分/题，共20分） （请将答案填入下表） 1 6 2 7 3 8 4 9 5 10 根据数据元素之间关系的不同特征，通常有集合、线性结构、树形结构、和 4种基本结构。 一个无向图完全图中，共有 条边。 假定一组记录的排序码为（49，38，65，97，76，13，27），对其进行归并排序的过程中，第三趟归并后的结果为__________________________________。 取出广义表A=（（x，y，z），（a，b，c））中原子b的函数是 。 二分查找法要求查找表中的数据元素应满足的条件是 。 单链表中指针P所指结点不为尾结点的条件是_____ ______。 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度与顺序表的个数和 有关。 如右图所示的二叉树，按中序遍历所得