2015年电大数据结构（本）选择题 精篇复习资料.doc

一、单项选择题(每小题2分，共30分)1.非空的单向循环链表的尾结点满足(c)(设头指针为head，指针p指向尾结点)。a.p-next=nullb.p=nullc.p-next=headd.p=head2.一种逻辑结构(a)。a.可以有不同的存储结构b.只能有唯一的存储结构c.是指某一种数据元素之间的存储关系d.以上三种说法均不正确3.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为(a)。a.物理结构b.逻辑结构c.算法的具体实现d.给相关变量分配存储单元4.在一个单链表中p所指结点之后插人一个s所指的结点时，可执行(d)。 a.p-next=s;s-next=p-next b.p-next=s-next c.p=s-next d.s-next=p-next;p-next=s5.在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为(b)a.f-next=s;f=sb.r-next=s;r=sc.s-next=r;r=sd.s-next=f;f=s6. 元素1,3,5,7按顺序依次进栈，则该栈的不可能输出序列是(c)(进栈出栈可以交替进行)。a.7,5,3,1 b.1,3,5,7 c.7,5,1,3 d.3,1,7,57.设有一个20阶的对称矩阵a，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组b中(数组下标从1开始)，则矩阵中元素a9,2在一维数组b中的下标是(d)。a.41 b.32 c.18 d.388.设有两个串p和q，求q在p中首次出现的位置的运算称作(d)。a.连接 b.求子串 c.求串长 d.模式匹配9.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为(a)。a.2i b.21一1 c.2i十1 d.2i十210.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有(d)个结点。a.2n b.2n十1 c.2n+2 d.2n一111.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为(d)。 a.abecdf b.acfebd c.aebcfd d.aedfcb12.线性表以(a)方式存储，能进行折半查找。a.关键字有序的顺序 b.顺序c.链接 d.二插树13.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为(d)。a.35/12b.39/12c.41/12d.37/1214.设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是(d)。a.折半排序b.冒泡排序c.归并排序d.简单选择排序15.一组记录的关键字序列为(47,80,57,39,41,46)，利用堆排序(堆顶元素是最小元素)的方法建立的初始堆为(a)。a.39,41,46,80,47,57b.39,47,46,80,41,57c.41,39,46,47,57,80d.39,80,46,47,41,571.链表所具备的特点是(c)。 a.可以随机访问任一结点 b.占用连续的存储空间 c.插人删除元素的操作不需要移动元素结点 d.可以通过下标对链表进行直接访问2.线性结构中数据元素的位置之间存在(a)的关系。 a.一对一 b.一对多 c.多对多d.每一个元素 都有一个直接前驱和一个直接后继3.算法的时间复杂度与(c)有关。 a.所使用的计算机 b.与计算机的操作系统 c.与算法本身 d.与数据结构4.在一个单链表中，p,q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是(c)。 a.p=q-next b.p-next=q c.p-next=q-next d.q-next=null5. 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为(c) a.r=f-next; b.r=r-next; c.f=f-next; d.f=r-next;6. 元素3,6,9按顺序依次进栈，则该栈的不可能输出序列是(b)(进栈出栈可以交替进行) a. 9,6,3 b. 9,3,6 c. 6,3,9 d. 3,9,67.设有一个10阶的对称矩阵a，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组b中(数组下标从1开始)，则矩阵中元素a8,5在一维数组b中的下标是(a)a.33 b.32 c.85 d.418.在c语言中，顺序存储长度为3的字符串，需要占用(a)个字节。a.4 b. 3 c.6 d. 129一棵有n个结点采用链式存储的二叉树中，共有(a)个指针域为空。a. n+1 b. n c. n-1 d. n-210.设一棵哈夫曼树共有n个叶结点，则该树有(a)个非叶结点。a.n-1 b. n c. n+1 d.2n11.在一个无向图中，所有顶点的度数之和等于边数的(d)倍 a.3 b.2.5 c.1.5 d.212. 已知如图所示的一个图，若从顶点v，出发，按广度优先进行遍历，则可能得到的一种顶点序列为(c)。 a.v1v2v3v6v7v4v5v8 b.v1v2v3v4v5v8v6v7 c.v1v2v3v4v5v6v7v8 d.v1v2v3v4v8v5v6v713.在有序表2,4,7,14,34,43,47,64,75,80,90,97,120中，用折半查找法查找值80时，经(a)次比较后查找成功。 a.4 b. 2 c. 3 d. 514.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少)，然后将其放入已排序序列的正确位置的方法是(c)。 a.冒泡 b.直接插入 c.折半插入 d.选择排序15.排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的一端的方法，称为(d)排序。 a.归并 b.插人c.快速 d.选择1.针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用(d)存储方式最节省时间。 a.单链表 b.双链表c.单循环链表 d.顺序表2.数据结构中，与所使用的计算机无关的是数据的(d)结构。 a.物理 b.存储c.逻辑与物理d.逻辑3.以下特征中，(d)不是算法的特性。a.有穷性 c.可行性b.确定性 d.有0个或多个输出4.设有一个长度为n的顺序表，要在第i个元素之前(也就是插人元素作为新表的第个元素)，则移动元素个数为(a)。 a. n-i+1 b. n-i c. n-i-1 d.i5.栈的插人删除操作在(d)进行。 a.栈底 b.任意位置 c.指定位置 d.栈顶6.以下说法正确的是(c)。 a.栈的特点是先进先出，队列的特点是先进后出 b.栈和队列的特点都是先进后出 c.栈的特点是先进后出，队列的特点是先进先 出 d.栈和队列的特点都是先进先出8.设有一个15阶的对称矩阵a，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组b中(数组下标从1开始)，则矩阵中元素a7,6。在一维数组b中的下标是(c)。 a.42 b. 13 c.27 d. 329.串函数strcmp (d,d)的值(b)。 a. 0 b. 1 c.-1 d. 310.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为(d) a. 2i b. 2i-1 c. 2i+2 d. 2i+111.设一棵有n个叶结点采用链式存储的二叉树，除叶结点外每个结点度数都为2，则该树共有(d)个指针域为空。 a. 2n b. 2n+ l c. 2n+2 d. n+ l12.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为(b)。 a.abeedfb. abeefdc. aebefdd. acfdeb 13.在有序表1,3,8,13,33,42,46,63,76,78,86,97,100中，用折半查找值86时，经(d)次比较后查找成功。 a.6 b. 3 c.8 d. 4 14.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为(a)。 a. 29/10 b. 31/10 c.26/10 d. 29/9 15.一组记录的关键字序列为(37,70,47,29,31,85)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为(a)。 a. 31,29,37,47,70,85 b. 29,31,37,47,70,85 c. 31,29,37,70,47,85 d. 31,29,37,85,47,702.以下说法中不正确的是(b)。 a.双向循环链表中每个结点需要包含两个指针域 b.已知单向链表中任一结点的指针就能访问到链表中每个结点 c.顺序存储的线性链表是可以随机访问的 d.单向循环链表中尾结点的指针域中存放的是头指针3.双向循环链表结点的数据类型为: struct node int data; struct node *next;/*指向直接后继*/ struct node *prior; ; 设p指向表中某一结点，要显示p所指结点的直接前驱结点的数据元素，可用操作(b)a. printf(%d,p-next-data);b. printf(%d,p-prior-data);c. printf(%d,p-prior-next);d. printf(%d,p-data);5.设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用x接收栈顶元素，则取栈顶元素的操作为(c)a.top-data= x; b.top= top-next;c.x=top-data;d.x=top-data; top= top-next;6.以下说法不正确的是(c)。 a.栈的特点是后进先出b.队列的特点是先进先出c.栈的删除操作在栈底进行，插人操作在栈顶进行 d.队列的插入操作在队尾进行，删除操作在队头进行7. char *p; p= strcat (abd,abc); printf(%s, p); 的显示结果为(b)。 a.-1 b. abdabc c.ab d. 18. 深度为5的满二叉树至多有(b)个结点(根结点为第一层)。 a. 40 b. 31 c. 34 d.359.已知一个图的所有顶点的度数之和为m，则该图的边数为(d)。 a. 2m b.m c. 2m+1 d. m/210.以下说法不正确的是(a)。 a.连通图g的生成树一定是唯一的 b.连通图g一定存在生成树 c.连通图g的生成树中一定要包含g的所有顶点 d.连通图g的生成树一定是连通而且不包含回路11.有序表为1,2,4,6,10,18,20,32，用课本中折半查找算法查找值18，经(b)次比较后成功查到。 a.3 b.2 c.4 d.512.在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是(a)。 a.冒泡b.选择c.直接插入 d.折半插入13.用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行(a)次元素间的比较。 a. 4 b. 3 c.5 d. 614.如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为(b) a.acfgedb b.aedbgfcc.acfebdg d.aecbdgf15.一棵哈夫曼树总共有25个结点，该树共有(a)个非叶结点(非终端结点)。 a.12 b. 13 c.14 d.151.从n个数中选取最大元素(c)。a.基本操作是数据元素间的交换b.算法的时间复杂度是o(n2)c.算法的时间复杂度是o(n)d.需要进行(n十1)次数据元素间的比较2.设head为非空的单向循环链表头指针，p指向链表的尾结点,则满足逻辑表达式(d)的值为真。a. p-next=null b. p=nullc. p-next=head d. p-next = head3.设顺序存储的线性表长度为n，要删除第i个元素,按课本的算法,当i =(c)时,移动元素的次数为3。a. 3 b. n/2 c. n-3 d. 35. 设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值，p为指向结点类型的指针，可执行如下操作:p=front-next; x=p-data;然后执行(b)。a. front=p-next; b. front -next=p-next;c. front=p; d. front-next =p;6. 在c语言中，存储字符串abcd需要占用(c)字节。a. 4 b. 2 c. 5 d. 37.设有一个10阶的对称矩阵a，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵a的第一个元素为al,1 ，数组b的下标从1 开始) ，则矩阵元素a5,3对应一维数组b的数组元素是(c)。a. b18 b. b8 c. b13 d. b108.深度为5的完全二叉树共有20个结点，则第5层上有(c)个结点。(根所在层为第一层)a. 3 b. 8 c. 5 d. 69.巳知一个图的所有顶点的度数之和为m，且m是以下4种情况之一，则m只可能是(d)a. 9 b. 7 c. 15 d. 810.线性表只要以(c)方式存储就能进行折半查找。a.链接 b.顺序c.关键字有序的顺序d.二叉树11.对n个元素进行冒泡排序若某趟冒泡中只进行了(c)次元素间的交换则表明序列已经排好序。a. 1 b. 2 c. 0 d. n-112.在对一组元素(64,48,106,33,25,82,70,55,93)进行直接插入排序时,当进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行(c)次元素间的比较(指由小到大排序)。a. 6 b. 2 c. 3 d. 413.如图，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为(b)。a. acebdgfb. abecdgfc. acfedgbd. abecfdg14.一棵哈夫曼树有10个非叶子结点(非终端结点), 该树总共有(a)个结点。a. 21 b. 20 c. 22 d. 191.数据元素是数据的基本单位,它(c)。a.只能有一个数据项组成b.至少有二个数据项组成c.可以是一个数据项也可以由若干个数据项组成d.至少有一个数据项为指针类型2.线性表的顺序结构中,(c)。a.逻辑上相邻的元素在物理位置上不一定相邻b.数据元素是不能随机访问的c.逻辑上相邻的元素在物理位置上也相邻d.进行数据元素的插入、删除效率较高3.以下表中可以随机访问的是(d)。a.单向链表b.双向链表c.单向循环链表d.顺序表4.设顺序存储的线性表长度为n,对于删除操作,设删除位置是等概率的,则删除一个元素平均移动元素的次数为(a)。a.(n+1)/2 c.2n b.n d.n-i5.设top是一个链钱的栈顶指针,战中每个结点由一个数据域data和指针域next组成,设用x接收钱顶元素,则出战操作为(a)。a.x=top-data;top=top-next;b.top=top-next;x=top-data;c.x=top-next;top=top-data;d.top-next=top;x=top-data;6.以下说法正确的是(c)。a.队列是后进先出b.栈的特点是后进后出c.栈的删除和插人操作都只能在栈顶进行d.队列的删除和插入操作都只能在队头进行7.串函数strcmp(b,cd)的值为(d)。a.1 b.0 c.bcd d.-18.设有一个12阶的对称矩阵a,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中(矩阵a的第一个元素为a1,1,数组b的下标从1开始),则矩阵a中第4行的元素在数组b中的下标i一定有(a)。a7=i=10b.11=i=15c.9=i=14d.6=inext=p;rear=p;b.rear