《《数据结构》选择题答案GY》由会员分享，可在线阅读，更多相关《《数据结构》选择题答案GY（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构期末复习题一、单选题 1某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ C ）。AO（n） BO（nlog2n） CO（n2） DO（log2n）2队列的插入操作是在（ B ）进行。A队首 B队尾 C队前 D对后3二叉树上叶结点数等于（ C ）。A分支结点数加1 B单分支结点数加1 C双分支结点数加1 D双分支结点数 减14每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ A ）排序A插入 B交换C选择 D归并5在一个图中，所有顶点的度数之和等于所有边数的（ A ）倍。A2 B1C3 D46队列的删除操作是在（ A ）进行。A队首
2、B队尾 C队前 D对后7当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ C ）语句修改top指针。Atop+; Btop=0; Ctop-; Dtop=N;8由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。A51 B23C53 D749在一棵二叉树中，第4层上的结点数最多为（ B ）。A31 B8C15 D1610 向堆中插入一个元素的时间复杂度为（ A ）。AO(log2n) BO(n) CO(1) D16 O(nlog2n)11在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时
3、，需要从后向前依次后移（ B ）个元素。An-i Bn-i+1Cn-i-1 Di12在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（ A ）。An/m Bm/n Cn/(n+m) Dm/(n+m)13从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ B ）。A原树高度加1 B原树高度减1 C原树高度 D不确定14在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ A ）。A行号 B列号 C元素值 D地址15在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ C ）条边。An B2nCn-1 Dn+1
4、16.17与上边重复18在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定（ A ）该结点的值。A小于 B大于C不小于 D大于等于19对于一棵具有n个结点的树，该树中所有结点的度数之和为（ A ）。An-1 Bn Cn+1 D2n20某程序的时间复杂度为（3n+100log2n+ nlog2n）, 其数量级表示为（ B ）。AO（n） BO（nlog2n） CO（100） DO（log2n）21. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ C ）。A. 2，3，5，8，6B. 3，2，5，8，6C.3，2，5，6，8D. 2，
5、3，6，5，822根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（ B ）。AO(n) BO(log2n ) CO(n2) DO(nlog2n) 23. 按照数据逻辑结构的不同，可以将数据结构分成 C 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构24. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构D. 用一维数组存储二叉树，总是以先序顺序遍历各结点 25. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，
6、称之为 B A.逻辑结构 B.顺序存储结构C.链式存储结构 D.以上都不对26. 以下关于算法特性的描述中， B 是正确的。 （1）算法至少有一个输入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去A. （1） B. （2） C. （3） D. （2）和（3）27. 对顺序存储的线性表（a1,a2,an）进行插入操作的时间复杂度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1)28. 链表不具有的特点是 A 。 A.可随机访问任一元素 B.插入和删除时不需要移动元素C.不必事先估计存储空间 D.所需空间与线性表的长度成正比29.线性链
7、表中各链结点之间的地址 C 。 A.必须连续 B.部分地址必须连续C.不一定连续 D.连续与否无关30. 以下关于链式存储结构的叙述中， C 是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除操作方便，不必移动结点31. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为 D 。A. dcba B. acdb C. abcd D. cbda32. 将新元素插入到链式队列中时，新元素只能插入到 B 。A. 链头 B. 链尾 C. 链中 D. 第i个位置，i大
8、于等于1，大于等于表长加133. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是 C 。 A. 6 B. 4 C. 3 D. 234.下面 D 是abcd321ABCD的子串。A. abcd B. 321ab C. abc ABC D. 21AB35.假设8行10列的二维数组A18，110分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a3，5的地址与以列序为主序时 C 元素相同。A. a7，3 B. a8，3 C. a1
9、，4 D. ABC都不对36. 数组A05，06的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址为 A 。 A. 1175 B. 1180 C. 1205 D.1210 37.下列广义表中，长度为3的广义表为 B 。A.（a,b,c,( )） B. (g),(a,b,c,d,f),( ) C. (a,(b,(d) D. ( )38. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( D )。 A. slink=plink; plink=s; B. plink=s; slink=q; C. plink
10、=slink; slink=p; D. q link=s; slink =p;39.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有 D 个叶结点。A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c40.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是 B 。A. 100 B. 101 C. 102 D. 103 41. 在有n 个叶子结点的霍夫曼树中，其结点总数为： D 。 A. n B. 2n C. 2n +1 D. 2n - 142.具有12个结点的完全二叉树有 B 。A. 5个叶子结点 B. 5个度为2的结点C. 7个分支结点 D. 2个度为1的结点43.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x在y之后，则x和y的关系是 C 。A. x是y的左兄弟 B. x是y的右兄弟C. x是y
