数据结构基本概念练习题1、选择练习题1）执行下面程序段时，执行S语句的次数为-------for(int I=1;I<=n;I++)for(int j=1;j<=I;j++)S;(A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2答案：D2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。
下列______不属于算法的五个特性之一。
(A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性答案：D3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
(A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表答案：A4）下面的叙述正确的是（）(A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比;(B) 线性表在链式存储时，查找第i个元素的时间同i的值无关;(C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比;(D) 以上说法都不对.答案：A5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
(A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表答案：B6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。
(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;答案：C7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
(A) 线性表的顺序存储结构(B) 队列(C) 线性表的链式存储结构(D) 栈答案：D8) 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。
(A) top=top+1; V [top]=x (B) V [top]=x; top=top+1 (C) top=top-1; V [top]=x(D) V [top]=x; top=top-1答案：C9）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )(A) 1和5 (B) 2和4 (C) 4和2 (D) 5和1答案：B10）设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。
(A) fedcba (B) bcafed (C) dcefba (D) cabdef答案：D11）假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
(A) 808 (B) 818 (C) 1010 (D) 1020答案：B12）数组A[0..4,-1..-3,5..7]中含有元素的个数（）。
(A) 55 (B) 45 (C) 36 (D) 16答案：B13）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
(A) i（i-1）/2+j (B) j（j-1）/2+i (C) i（j-i）/2+1 (D) j（i-1）/2+1答案：B14）对稀疏矩阵进行压缩存储目的是（）。
(A) 便于进行矩阵运算(B) 便于输入和输出(C) 节省存储空间(D) 降低运算的时间复杂度答案：C15) 对广义表L=(a,())执行操作tail(L)的结果是( )(A) () (B) (()) (C) a (D) (a)答案：B16) 具有10个叶结点的二叉树中至少有（）个度为2的结点(A) 8 (B) 9 (C) 10 (D) 11答案：B17）当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）(A) A[2i](2i<=N) (B) A[2i+1](2i+1<= n) (C) A[i/2] (D) 无法确定答案：D18）二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。
该二叉树根的右子树的根是( )(A) E (B) F (C) G (D) H答案：C19）由3 个结点可以构造出多少种不同的二叉树？（）(A) 2 (B) 3 (C) 4 (D) 5答案：D20）n个结点的线索二叉树上含有的线索数为（）(A) 2n (B) n－l (C) n＋l (D) n答案：C21）数据结构的定义为（d，R），其中d是的集合。
B（A) 算法 (B) 数据元素 (C) 数据操作 (D) 逻辑结构22）基本的逻辑结构包括( D )。
(A) 树型结构、图状结构、线性结构和非线性结构(B) 集合结构、线性结构、树型结构和非线性结构(C) 集合结构、树型结构、图状结构和非线性结构(D) 集合结构、线性结构、树型结构和图状结构23）数据结构是一门研究计算机中对象及其关系的学科。
B(A) 数值预算 (B) 非数值运算 (C) 集合 (D) 非集合23）下面程序段的时间复杂度为（C ）。
for (i=1;i<=m;++i)for (j=1;j<=n;++j)A[i,j]=i*j;注：m的平方表示为m^2(A) O（m^2） (B) O（n^2） (C) O（m*n） (D) O（m+n）24）数据的运算定义在数据的逻辑结构上，只有确定了( C )，才能具体实现这些运算。
(A) 数据对象 (B) 逻辑结构 (C) 存储结构 (D) 数据操作25）下面程序段执行的时间复杂度为( C )。
for(i=1;i<=n;i++)for(j=1;j<=i;j++) s++;(A) O(n) (B) O(lgn) (C) O(n^2) (D) O(n^3)26）对于顺序表的优缺点，以下说法错误的是( C )。
(A) 无需为表示结点间的逻辑关系而增加额外的存储空间(B) 可以方便地随机存取表中的任一结点(C) 插入和删除运算较方便(D) 容易造成一部分空间长期闲置而得不到充分利用27）对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）。
(A) head==NULL (B) head->next==NULL （C) head->next==head (D) head!=NULL28 一个顺序表第一个元素的存储地址是100，每个元素的存储长度为4，则第5个元素的地址是( B )。
(A) 110 (B) 116 (C) 100 (D) 12029）当对线性表的操作是以插入操作和删除操作为主时或当线性表的长度不能确定或表长变化很大时，应选择( B )作为线性表的存储结构。
(A) 顺序表 (B) 链表 (C) 栈 (D) 队列30）设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。
(A) 单链表 (B) 单循环链表 (C) 带尾指针的单循环链表 (D) 带头结点的双循环链表31）在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( C )。
(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;32）在一个单链表中，若删除P结点的后继结点，则__A___(A) p->next = p->next->next;(B) p = p->next; p->next = p->next->next;(C) p->next = p->next;(D) p = p->next->next;33）若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ B ）存储方式最节省时间。
(A) 单链表 (B) 顺序表 (C) 单向循环链表 (D) 双链表34）一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）。
(A) 不确定 (B) n-i+1 (C) i (D) n-i35）设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。
(A) XYZ (B) YZX (C) ZXY (D) ZYX36）用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。
(A) 仅修改队头指针(B) 仅修改队尾指针(C) 队头、队尾指针都要修改(D) 队头,队尾指针都可能要修改37）串的长度是指（B ）(A) 串中所含不同字母的个数 (B) 串中所含字符的个数(C) 串中所含不同字符的个数 (D) 串中所含非空格字符的个数38）二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。
若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。
设每个字符占一个字节。
(A) A[8,5] (B) A[3,10] (C) A[5,8] (D) A[0,9]39）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。
(A) 先序 (B) 中序 (C) 后序 (D) 从根开始按层次遍历40）在中国，孔氏家族是影响最大的家族。