哈尔滨师范大学-数据结构

出自:哈尔滨师范大学-数据结构

(单选题) 按照二叉树的定义,具有3个结点的二叉树有( )种。(本题2.0分) A、 3 B、 4 C、 5 D、 6

(单选题) 邻接表的存储结构下图的广度优先遍历类似于二叉树（树）的( )。(本题2.0分) A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历

(单选题) 对有n个记录的有序表采用二分查找，其平均查找长度的量级为（）。(本题2.0分) A、 O(log2n) B、 O(nlog2n) C、 O(n) D、 O(n2)

(单选题) 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省空间。(本题2.0分) A、单链表 B、双链表 C、带头结点的双循环链表 D、单循环链表

(单选题) 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。(本题2.0分) A、 2*n B、 2*e C、 n D、 e

(单选题) 有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（）。(本题2.0分) A、 13 B、 33 C、 18 D、 40

(单选题) 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（）。(本题2.0分) A、 n*n B、 n*(n+1)/2 C、 (n+1)*(n+1)/2 D、 (n-1)*n/2

(单选题) 数组b[1..10，-2..6，2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。元素b[5,0,7]的存储首址为（）。(本题2.0分) A、 900 B、 912 C、 910 D、 913

(单选题) 已知广义表a=((a,b,c)，(d,e,f))，从a中取出原子e的运算是（）。(本题2.0分) A、 tail(head(a)) B、 head(tail(a)) C、 head(tail(tail(head(a)))) D、 head(tail(tail(a)))

(单选题) 已知广义表ls=(a,(b,c,d),e)，运用head和tail函数取出ls中原子b的运算是（）。(本题2.0分) A、 head(head(ls)) B、 tail(head(ls)) C、 head(head(tail(ls))) D、 head(tail(ls))

(单选题) 设有5000个元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用那一种最好（）。(本题2.0分) A、快速排序 B、堆排序 C、归并排序 D、基数排序和shell排序

(单选题) 链栈和顺序栈相比，有一个较明显的优点是( )。(本题2.0分) A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更加方便 D、删除操作更加方便

(单选题) 非空的循环单链表（头指针为 head ）的尾结点（由 p 指向）满足【】。(本题2.0分) A、 p->next==NULL B、 p==NULL C、 p->next==head D、 p==head

16. (填空题) 数据结构一般包括___、___和数据运算三个方面的内容。(本题3.0分)

17. (填空题) 设有一批数据元素,为了最快地存取某元素,宜用___结构存储,为了方便地插入一个元素,宜用___结构存储。(本题3.0分)

18. (填空题) 栈和队列都是___结构;对于栈,只能在___插入和删除元素;对于队列,只能在___插入元素,在___删除元素。(本题3.0分)

19. (填空题) 深度为k的完全二叉树至多有___个结点,至少有2k-1+1个结点。(本题3.0分)

20. (填空题) 邻接表是图的___存储结构。(本题3.0分)

21. (填空题) 在顺序表中访问任意一结点的时间复杂度均为___,因此,顺序表也称为___的数据结构。(本题3.0分)

22. (填空题) 设一棵完全二叉树有700个结点,则共有 ___ 个叶子结点。(本题3.0分)

23. (填空题) 数据结构是一门研究非数值计算的程序设计问题中计算机的___ 以及它们之间的___ 和运算等的学科。(本题3.0分)

24. (填空题) 在树形结构中,树根结点没有___结点,其余每个结点有且只有 ___个前驱结点;叶子结点没有 ___ 结点,其余每个结点的后续结点可以 ___ 。(本题3.0分)

25. (填空题) 在双链表中,每个结点有两个指针域,一个指向___ ,另一个指向 ___。(本题3.0分)

(判断题) 在链表中存储线性表中的第一个数据元素的结点是首元结点。（）(本题1.0分) A、正确 B、错误

(判断题) 空格串是指由空格字符所组成的字符串，其长度等于空格个数。（）(本题1.0分) A、正确 B、错误

(判断题) 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【】。(本题1.0分) A、正确 B、错误

(判断题) 二分查找可以在有序的双向链表上进行。 ( )(本题1.0分) A、正确 B、错误

(判断题) 线性表采用顺序存储表示时，必须占用一片连续的存储单元。（）(本题1.0分) A、正确 B、错误

(判断题) 含零个字符的串称为空串。任何串中所含字符的个数为该串的长度。(本题1.0分) A、正确 B、错误

(判断题) 模式串P=’abaabcac’的next函数值序列为01122313。（）(本题1.0分) A、正确 B、错误

(判断题) 队列在函数调用时必不可少，因此递归离不开队列。 ( )(本题1.0分) A、正确 B、错误

(判断题) 顺序存储方式只能用于存储线性结构。 ( )(本题1.0分) A、正确 B、错误

36. (问答题) 在单链表、双向循环链表和单循环链表中,若仅知道指针 p 指向某结点,不知道头指针,能否将结点 p 从相应的链表中删除?若可以,时间复杂度各为多少。(本题15.0分)

37. (问答题) 阐述顺序表和链表存储方式的特点(本题15.0分)

(单选题) 线性表以链式方式存储，访问第i 个结点的时间复杂度为【】。(本题2.0分) A、 Oi B、 O1 C、 On D、 Oi-1

(单选题) 循环链表H 尾结点 p 的特点是【】。(本题2.0分) A、 p->next==H B、 p->next==H->next C、 p==H D、 p==H->next

(单选题) 对于栈操作数据的原则是【】。(本题2.0分) A、先进先出 B、后进后出 C、后进先出 D、不分顺序

(单选题) 队列的先进先出特征是指【】。(本题2.0分) A、最后插入队列的元素总是最后被删除 B、当同时进行插入、删除操作时，总是插入操作优先 C、每当有删除操作时，总要先做一次插入操作 D、每次从队中删除的元素总是最早插入的元素

(单选题) 与顺序栈相比较，链栈有一个比较明显的优势是【】。(本题2.0分) A、通常不会出现栈满的情况 B、插入操作更容易实现 C、通常不会出现栈空的情况 D、删除操作更容易实现

(单选题) 如果某图的邻接矩阵时对角线元素均为零的上三角矩阵，则此图是（）。(本题2.0分) A、有向完全图 B、连通图 C、强连通图 D、有向无环图

(单选题) 为了方便的在线性结构的数据中插入一个数据元素，则其数据结构宜采用（）。(本题2.0分) A、顺序存储 B、链式存储 C、索引存储 D、散列存储

(单选题) 某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（）。(本题2.0分) A、 210 B、 208 C、 216 D、 220

(单选题) 不带头结点的单链表head为空的判断条件是( )。(本题2.0分) A、 head==NULL B、 head->next==NULL C、 head->next==head D、 .head!=NULL

(单选题) 带头结点的单链表head为空的判断条件是( )。(本题2.0分) A、 head==NULL B、 head->next==NULL C、 head->next==head D、 head!=NULL

16. (填空题) 线性表的两种存储结构顺序存储方式和链式存储方式中,__存储方式要求逻辑上相邻的物理位置上也相邻,__存储方式不要求逻辑上相邻的物理位置上也相邻。(本题3.0分)

17. (填空题) 在链表中进行元素的插入和删除时,不需要移动结点,只需要改变相关结点的__或者___域。(本题3.0分)

18. (填空题) 抽象数据类型可用(D,S,P)三元组表示,其中,D是__对象,S是D上的__集,P是对D的基本操作集合

19. (填空题) 查找时的基本操作是“将记录的关键字和给定值进行__”。衡量查找方法好坏的标准是查找算法在查找成功时的平均__长度。(本题3.0分)

20. (填空题) 若一个图中有n个顶点和e条边,每个顶点的度为di,那么e若用di表示, 则e=__。(本题3.0分)

21. (填空题) 数据的逻辑结构可分为___、___两大类。(本题3.0分)