一、是非题
1. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。.......................( T )
2. 线性表的逻辑顺序与物理顺序总是一致的........( F )
3. 线性表中的每个结点最多只有一个前驱和一个后继。......( T )
4. 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................( F )
5. 栈和队列逻辑上都是线性表。..........................( T )
6. 单链表从任何一个结点出发，都能访问到所有结点........( F )
7. 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................( T )
8. 在用单链表表示的链式队列中，队头在链表的链尾位置。....( F )
9. 多维数组是向量的推广。..............................( T )
10. 栈是一种先进先出的线性表。....( F )
11. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T )
12. 设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F )
13. 一般树和二叉树的结点数目都可以为0。................( F )
14. 按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。....( T )
15. 后序序列和中序序列能唯一确定一棵二叉树。....( T )
16. 对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n) .............( T )
17. 网络的最小代价生成树是唯一的。...( T )
18. 图的拓扑有序序列不是唯一的。...( T )
19. 进行折半搜索的表必须是顺序存储的有序表。...( T )
二、 单选题
1. 算法指的是（ D ）
A．计算机程序        B．解决问题的计算方法
C．排序算法          D．解决问题的有限运算序列
2. 线性表采用链式存储时，结点的存储地址（B  ）
A．必须是不连续的    B．连续与否均可
C．必须是连续的      D．和头结点的存储地址相连续
3. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C  ）
A．O（1）        B．O（n）    C．O（m）    D．O（m+n）
4. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。
A．O(n)        B．O(1)      C．O(n2)      D．O(log2n)T
5. 线性表L在( B )情况下适用于使用链式结构实现。
A.需经常修改Ｌ中的结点值  B.需不断对Ｌ进行删除插入
C.L中含有大量的结点      D.L中结点结构复杂
6. 设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B )
A．s一>1ink=p一>1ink；p一>1ink＝s
B．q一>1ink＝s；s一>link=p
C．p一>link＝s一>1ink；s一>1ink＝p
D．p一>1ink＝s；s一>1ink＝q
7. 已知指针p所指不是尾结点，若在*p之后插入结点*s，应执行下列哪个操作 (B)
  A. s->link = p； p->link = s；
  B. s->link = p->link； p->link = s；
  C. s->link = p->link； p = s；
  D. p->link = s； s->link = p；
二叉树的基本性质
8. 非空的循环单链表first的尾结点（由p所指向）满足：(C)
  A. p->link == NULL；
  B. p == NULL；
  C. p->link == first；
  D. p == first；
9. 若让元素1，2，3依次进栈，则出栈次序不可能出现( C )种情况。
A．3，2，1        B．2，1，3
C．3，1，2        D．1，3，2
10. 若进栈序列为1234，则不可能得到的出栈序列是  C  。
A）3，2,1，4    B）3,2，4,1，  C）4,2，3,1      D）2,3，4,1
11. 由两个栈共享一个向量空间的好处是：（B  ）
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
12. 对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................(D  )
A．R-F    B.n+R-F    C.(R-F+1)mod n    D.(n+R-F）mod n
13. 在一个链队列中,假定front和rear分别为队首和队尾指针，则插入指针s所指的结点的操作为  C    。
A）front->next=s;        B)s->next=rear;rear=s;
C)rear->next=s;rear=s;    D)s->next=front;front=s;
14. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ D ）
A．front=front+1                B．front=(front+1)%(m-1)
C．front=(front-1)%m            D．front=(front+1)%m
15. 如下陈述中正确的是（A  ）
A．串是一种特殊的线性表        B．串的长度必须大于零
C．串中元素只能是字母          D．空串就是空白串
16. 一个非空广义表的表头（ D ）
A．不可能是子表           B．只能是子表
C．只能是原子             D．可以是子表或原子
17. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程(B  )。
A.较快    B.较慢        C.相同        D.不一定
18. 树中所有结点的度等于所有结点数加( C )。
A.0          B.1          C.一1            D.2
19. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于( C )。
A.n          B.n一1    C.n+1        D.2*n
20. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是 B 的二叉树。
A）空或只有一个结点。              B）高度等于其结点数。
C）任一结点无左孩子。              D）任一结点无右孩子。
21. n个结点的二叉树，若用二叉链表存贮则非空闲的左、右孩子链域为C。
A）n      B)2n        C)n-1      D)n+1
22. 在有n个叶子结点的哈夫曼树中，其结点总数为   D  。(性质3)
 A） 不确定    B） 2n      C） 2n + 1      D）2n - 1
23. 已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为B。
A  130        B  129          C  131          D  不确定
24. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为(  C  )
A．4          B．5            C．6          D．7
25. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是(  C  )
A．O(n)        B．O(e)        C．O(n+e)    D．O(n*e)
26. 在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个(  A  )。
A、顶点序列    B、边序列 C、权值总和    D、边的条数
27. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
        20，15，21，25，47，27，68，35，84
        15，20，21，25，35，27，47，68，84
        15，20，21，25，27，35，47，68，84
    则所采用的排序方法是（ D  ）
A．选择排序    B．希尔排序    C．归并排序    D．快速排序
28. 适于对动态查表进行高效率查的组织结构是（ C  ）
A．有序表      B．分块有序表  C．三叉排序树  D．线性链表
29. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用(D)方法最快。
A、起泡排序    B、快速排序      C、堆排序    D、直接选择排序
三、填空题
1. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的  存储结构  无关，是独立于计算机的。
2. 评价数据结构的两条基本标准是：    存储需要量  和  运算的时间效率  。
3. 算法的五个特性是指 有穷性 、确定性、 可行性 、输入和输出 。
4. 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=  p－>next－>next     。
5. 设单链表中指针P指向结点m，若要删除m之后的结点（若存在），则需修改指针的语句是：   P->next=p->next->next 
6. 设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为  3  。
7. 栈的特点是：后进先出，栈顶的位置是随着 进栈 和 出栈_操作而变化的。
8. 若有一个栈的输入序列为1,2,3,….n，输出序列的第一个元素为n，则第i个输出元素是n-i+1
9. 队列的特点是：先进先出，其插入操作在 队尾 进行，删除操作在 队头 进行。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。