计算机应用基础数据结构部分试题及答案
1．选择题：
1.下面程序段的时间复杂度的量级为（）
for(i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x=x+1;
A. O(1)
B.O(n)
C. O(n2)
D.O(n3)
2.在数据结构中，从逻辑上可以把数据结构分成（）
A. 动态结构和静态结构
B.紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D.内部结构和外部结构
3．数据结构的（）包括集合、线性、树形和图形结构四种基本类型。
A. 存储结构
B.逻辑结构
C. 基本运算
D.算法描述
4．数据的（）包括查找、插入、删除、更新和排序等。
A. 存储结构
B.逻辑结构
C. 基本运算
D.算法描述
5．数据的存储结构包括顺序、链接、散列和（）四种基本类型。
A. 线性
B.数组
C. 集合
D.索引
6．下面（）的时间复杂性最好，即执行时间最短。
A. O(n)
B.O(logn)
C. O(nlogn)
D.O(n2)
7.下面程序段的时间复杂性的量级为（）
for(int i=0;i for (int j=0;j a[i][j]=i*j; A. O(m2) B.O(n2) C. O(m*n) D.O(m+n) 8．（）不是算法的基本特征。 A. 正确性 B. 长度有限 C.在规定时间内完成 D. 确定性 9．一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列。 A. 31245 B.41325 C.23415 D.14253 10．在有n个结点的二叉链表中，值为空的链域个数为（）。P.109 A. n-1 B. 2n-1 C. n+1 D. 2n+1 1-5 D C B C D 6-11 B C C C C 11．已知完全二叉树有30个结点，则整个二叉树有（）个度为1的结点。 A. 0 B. 1 C. 2 D. 不确定 12．深度为k的完全二叉树至少有（）个结点。 A. 2k-1 B. 2k-2 C. 2k-1 D. 2k-2 13．深度为k的完全二叉树至多有（）个结点。 A. 2k-1 B. 2k-2 C. 2k-1 D. 2k-2 14．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。 A. 1 B. 2 C. 3 D. 4 15．折半查找有序表（6，15，30，37，65，68，70，72，89，99），若查找元素 37，需依次与表中元素（）进行比较。 A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，37 16．一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（）个元素。 A. n-i B. n-i+1 C. n-i-1 D. I 17．如图所示的4棵二叉树中，（）不是完全二叉树。 （A）(B) (C) (D) 18．对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的查找长度为（）。 A. 3 B. 4 C.5 D.6 19．设有10000个无序元素，希望用最快的速度挑选出其中前10个最大元素，最好选用（）排序法。 A. 堆排序 B. 快速排序 C. 起泡排序 D. 插入排序20．计算机算法指的是（）。 A. 计算方法 B. 排序方法 C.解决问题的有序序列 D. 调度方法11-15 B C A C D 16-20 B A B A C 21．一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（）。 A. 1，2，3，4 B. 4，3，2，1 C. 1，3，4，2 D. 4，1，2，3 22．对于任何一棵二叉树，如果其终端结点数为N0，度为2的结点数为N2，则N0=（）。 A. N2-1 B. N2+1 C. N2 D. N2-2 23．线性表是（） A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 24．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（） A. （n+1）/2 B.n/2 C. n D.n+1 25．在一个顺序表的表尾插入一个元素的时间复杂度的量级为（） A. O(n) B.O(1) C. O(n2) D.O(logn) 26．设单链表中指针p指向结点ai,若要删除ai之后的结点（若存在），则需修改指针的操作为（）。 A. p->next= p->next->next B. p=p->next C. p=p->next->next D. next=p 27．设单链表中指针p指向结点a i,指针f指向将要插入的新结点x，则当x插在链表中两个数据元素a i和a i+1之间时，只要先修改（）后修改（）即可。 A. p->next= f B. p->next= p->next->next C. p->next=f->next D. f->next= p->next E. f->next=null F. f->next=p 28．设单链表中指针p指向结点a i,指针f指向将要插入的新结点x，则在链表中最后一个结点a n之后插入时，只要先修改（）后修改（）即可。 A. f->next= p B. f->next= p->next C. p->next=f D. p->next= f->next E. f =null 29．在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。 A. 1 B. 2 C. 3 D.4 30．在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂性的量级为（） A. O(n) B.O(n/2) C. O(1) D.O(n1/2) 21-25 D B A C B 26-30 A (D.A) (B.C) B A 31．不带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL C. L->next = = L D. L! = NULL 32．带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL C. L->next = = L D. L! = NULL 33．在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D.6 34．在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（） A. p->prior B. p->next C. p->next->next D. p->prior ->prior 35．对一个具有n个元素的线性表，建立其单链表的时间复杂度为（） A. O(n) B.O(1) C. O(n2) D.O(logn) 36．线性表采用链式存储时，其地址（） A. 必须是连续的 B. 一定是不连续的 C. 部分地址必须是连续的 D. 连续与否均可以 37．假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top= =-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（） A. a[--top]=x B. a[top--]=x C. a[++top]=x D .a[top++]=x 38．若已知一个栈的入栈序列是1，2，3，…..n，其输出序列为p1, p2, p3,….. pn，若p1=n，则pi为（） A. i B.n-i C. n-i+1 D.不确定 39．判定一个栈S（最多元素为m0）为空的条件是（） A. S. top!=0 B. S. top= =0 C. S. top!=m0 D .S. top= =m0 40．判定一个栈S（最多元素为m0）为满的条件是（） A .S. top!=0 B. S. top= =0 C. S. top!=m0-1 D .S. top= =m0-1 31-35 A B C B A 36-40 D C C B D 41．一个队列的入队序列是1，2，3，4，则队列的输出序列是（） A.4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D .3，2，4，1 42．从一个顺序循环队列中删除元素时，首先需要（） A. 前移队首指针 B. 后移队首指针 C. 取出队首指针所指位置上的元素 D . 取出队尾指针所指位置上的元素43．假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队列空的条件为（） A.front+1= =rear B.rear+1= =front C. front= =0 D . front= =rear 44．假定一个顺序循环队列存储于数组a[N]中，其队首和队尾指针分别用front 和rear表示，则判断队列满的条件为（） A. （rear-1）%N= =front B. （rear+1）%N= =front C. （front-1）%N= =rear D . （front+1）%N= =rear 45．树中所有结点的度等于所有结点数加（） A.0 B.1 C.-1 D.2 46．在一棵树中，每个结点最多有（）个前驱结点。 A.0 B.1 C.2 D.任意多个 47．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点点数为2个，则度为0的结点数为（）个。 A.3 B.4 C.5 D.6 48．在一棵二叉树上第5层的结点数最多为（） A.16 B.15 C.8 D.32 49．在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。 A.2i B. 2i+1 C. 2i-1 D. 2n 50．一颗具有35个结点的完全二叉树的深度为（） A.6 B.7 C.5 D.8 41-45 B B D B C 46-50 B D A C A 51．在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点的编号为（） A.2i B.2i-1 C.2i+1 D.2i+2 52．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（） A.2h B.2h-1 C.2h+1 D.h+1 53．按照二叉树的定义，具有3个结点的二叉树有（）种状态。 A.5 B.4 C.3 D.30 54．若查找每个元素的概率相等，则在长度为n的顺序表上查找任意元素的平均查找长度为（） A.n B.n+1 C.（n-1）/2 D.（n+1）/2 55．顺序查找法适合于存储结构为（）的线性表。 A.散列存储 B.顺序存储或链接存储 C.压缩存储 D.索引存储 56．对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用折半查找，则查找元素26的查找长度（） A.2 B.3 C.4 D.5 57．对线性表进行折半查找时，要求线性表必须（） A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序 58．采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）A. O(n2) B. O(nlogn) C. O(n) D. O(logn) 59．在对n个元素进行直接插入排序的过程中，共需要进行（）趟。 A .n B.n+1 C.n-1 D.2n 60．对n个元素进行直接插入排序时间复杂度为（） A. O(1) B. O(n2) C. O(n) D. O(nlog2n) 51-55 C B A D B 56-60 C C D C B 61．在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟。 A. n B. n/2 C. logn D. 2n 62．在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。 A. 1 B. n C. n-1 D. n/2 63．在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（） A. O(1) B. O(logn) C. O(n2) D. O(nlogn) 64．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） A. 插入排序 B. 起泡排序 C. 希尔排序 D. 选择排序 65．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： （1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 则采用的排序方法是（）。 A. 选择排序 B. 希尔排序 C. 插入排序 D. 快速排序 66．对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。 A. 1，3，5，7，9 B. 5，7，9，1，3 C. 5，3，1，7，9 D. 9，7，5，3，1 67．若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（） A. O(1) B. O(logn) C. O(n) D. O(n2) 68．若对n个元素进行堆排序，则在由初始堆进行每趟排序的过程中，共需要进行（）次筛运算。 A. n+1 B. n/2 C. n D. n-1 69．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一段的方法，称为（）。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 70．一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建 立的初始堆为（）。 A. （80，45，55，40，42，85） B. （85，80，55，40，42，45） C. （85，80，55，45，42，40） D. （85，55，80，42，45，40） 61-65 C A D A D 66-70 B C D D B 71．若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（）。 A. 1 B.i-1 C.i D. i+1 72．在对n个元素进行冒泡排序的过程中，第一趟至多需要进行（）次相邻元素之间的比较。 A. n+1 B. n/2 C. n D. n-1 73．若一个元素序列基本有序，则选用（）排序较快。 A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序 74．快速排序方法在（）情况下最不利于发挥其长处。 A.要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 75．排序方法中，将整个无序序列分割成若干个小的子序列并分别进行插入排序的方法，称为（）。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序76．用直接插入排序方法对下列4个表由小到大进行排序，比较次数最少的是（）。 A. （94，32，40，90，80，46，21，69） B. （21，32，46，40，80，69，90，94） C. （32，40，21，46，69，94，90，80） D. （90，69，80，46，21，32，94，40） 77．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序方法，以第一个纪录为基准得到的一次划分结果为（）。 A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，46，84，56，79） 78．如果对元素序列（7，2，5，8，1，11）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）。 A.（1，2，5，7，8，11） B.（1，2，5，8，7，11） C.（1，5，2，7，8，11） D.（1，5，2，8，11，7） 79．如图所示，该二叉树的前序遍历序列是（）。 A. EGFACDB B. EAGCFBD C. EACBDGF D. EGACDFB 80．已知某二叉树的后序遍历序列是DACBE，中序序列是DEBAC，则它的前序遍历序列是（）。 A. ACBED B. DEABC C. DECAB D. EDBAC 71-75 C D C C A 76-80 B C B C D 81．已知某二叉树的前序遍历序列是ABDEFGC，中序序列是DEBGFAC，则对应的二叉树为（）。 81-85 B 2．填空题 1．数据结构及数据的逻辑结构包括_____,______,______,________四种类型。2．数据的存储结构及物理结构包括_____,______,______,________四种基本类型。 3．数据结构是研究数据的_____，_____以及它们之间的相互关系，并对这种结构定义相应的_____，设计出相应的_____，而确保经过这些运算后所得到的新结构是_____结构类型。 4．一个算法应具有_____，_____，_____，_____，_____这五个特征。 5．一个算法的时间复杂度是该算法包含的_____的多少，它是一个算法运行时间的相对度量，一个算法的空间复杂性是指该算法在运行过程中临时占用的_____的大小。 6．一个算法的时间复杂性通常用它的_____形式表示，当一个算法的时间复杂度与问题的规模n大小无关时，则表示为_____；成正比时，则表示为_____； 成对数关系时，则表示为_____；成平方时，则表示为_____。 7．_____是描述客观事物的数、字符以及所有能输入到计算机且被计算机程序加工处理的符号集合。_____是数据的基本单位，有时这个单位由若干个_____组成，在这种情况下，又称它为记录，_____是数据的最小单位，而由记录组成的线性表为_____。 8．一种数据结构的元素集合K和他的二元关系R为： K={a,b,c,d,e,f,g,h} R={ 该数据结构具有_____结构。 9．一种数据结构的元素集合K和他的二元关系R为： K={a,b,c,d,e,f,g,h} R={ 该数据结构具有_____结构。 10．一种数据结构的元素集合K和他的二元关系R为： K={1,2,3,4,5,6} R={(1,2), (2,3) ,(2,4), (3,4), (3,5), (3,6), (4,5), (4,6)} 该数据结构具有_____结构。 1．集合、线性结构、树型结构、图形结构（网状结构） 2．顺序存储、链式存储、散列、索引 3．物理结构、逻辑结构（二者顺序可颠倒）、运算、算法、原来的 4．有穷性、确定性、可行性、输入性、输出性 5．语句执行次数、存储空间 6．数量级、O(1)、O(n)、O(logn)、O(n2) 7．数据、数据元素、数据项、数据项、文件 8．线性结构 9．树型结构 10．图形结构（网状结构） 11．若经常需要对线性表进行插入和删除运算，则最好采用_____存储结构，若经常需要对线性表进行查找运算，则最好采用_____存储结构。 12．访问一个线性表中具有给定值元素的时间复杂性的量级为_____。13．对于一个长度为n的顺序表，在表头插入元素的时间复杂性为_____，在表尾插入元素的时间复杂性为_____。 14．在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_____的值赋给q->next，然后把_____的值赋给p->next。 15．在一个单链表中的p所指向结点之前插入一个指针s所指向的结点时，可执行如下操作： （1）s->next=_____; (2) p->next= s； (3) t= p->data； (4) p->data=_____； (5) s->data=_____； 16．假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行_____赋值操作，然后执行_____赋值操作。17．在一个单链表中删除指针p所指向结点的后继结点时，需要把_____的值赋给p->next指针域。 18．在一个单链表中删除指针p所指向结点时，应执行一下操作：q=p->next; p->data= p->next->data; p->next=_____； free(q); 19．在_____链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。 20．在一个带有头结点的双向循环链表中的p所指向的结点之前插入一个指针s 所指向结点时,可执行如下操作： （1）s->data= element; (2) s ->prior=_____； (3) p->prior->next=s; (4) s->next=_____; (5) p->prior=_____; 11．链式、顺序 12．O(n) 13．O(n)、O(1) 14．p->next、q 15．p->next、s->data、t 16．p->next= head、head=p 17．p->next->next 18．p->next->next 19．循环 20．p->prior、p、s 21．在一个双向链表中指针p所指向结点之前插入一个新结点时，其时间复杂性的量级为_______。 22．线性表的长度是指_______。 23．在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的，在线性表的链式存储中，元素之间的逻辑关系是通过_______决定的。 24．根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_______和_______。 25．线性表、栈和队列都是_______结构，对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素，在______删除元素。 26．设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push ,pop, push ,push后，对应的输出序列是_______。 27．设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为push(S,1),push(S,2), ______，pop(S)，push(S,4)，pop(S)，______，______,pop(S)，pop(S)。 28．在一个具有n个存储单元的循环队列中，当队列满时共有______个元素。 29．有一棵树如图所示，回答下列问题： （1）这棵树的根结点是（）； （2）这棵树的叶子结点是（） （3）结点C的度是（），这棵树的度是（） （4）结点C的子女是（） （5）结点C的父结点是（） 30．对于一个具有n个结点的二叉树，它可能具有的最小深度为______，具有的最大深度为______。 21．O(1) 22．线性表中包含数据元素的个数 23．物理存储地址、指针的值 24．单链表、双链表 25．线性、栈顶、队尾、队头 26．2，3 27．push(S,3)、pop(S)、push(S,5) 28．n-1 29．(1) A (2) B,E,G,D (3) 2,3 (4) E,F (5) A 30．[log2n]+1、n 31．一棵深度为k的满二叉树的结点总数为______，一棵深度为k的完全二叉树的结点总数的最小值为______，最大值______。 32．由a,b,c三个结点构成的二叉树，共有______种不同的结构。 33．对于一棵具有n个结点的树，该树中所有结点的度数之和为______。34．在一棵二叉树中，假定度为2的结点数为5个，度为1的结点数为6个，则叶子结点数为______个。 35．假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a[0]元素中，让编号为2的结点存入a[1]元素中，其余类推，则编号为i结点的左孩子结点对应的数组下标为______，右孩子对应下标为______。 36．一棵n个结点的完全二叉树从根结点这一层开始，每一层上的结点按从左到右的顺序存储于数组A[1….n]中，设某个结点在数组中的位置为i（1≤i≤n），则其父结点的位置是_______。 37．设二叉树的深度为h，且只有度为0和2的结点，则此二叉树中所含结点数最多为_______。 38．假定一组记录为（46,79,56,38,40,84），在冒泡排序的过程中进行第一趟排序后的结果为_______。 39．假定一组记录为（46,79,56,38,40,80），对其进行快速排序的过程中，共需要______趟排序。 40．假定一组记录为（46,79,56,38,40,80），对其进行快速排序，则第一次划分后的结果为______。 31．2k-1、2k-1、2k-1 32．5 33．n-1 34．6 35．2i-1、2i 36．[i/2](取整数部分) 37．2h-1 38．46,56,38,40,79,84 39．3 40．[40,38],46,[56,79,80] 41．对n个记录的有序表进行折半查找时，最大的比较次数是______。 42．折半查找法的存储结构仅限于______，且是有序的。 43．在单链表中，要删除某一指定的结点，必须找到该结点的______。 44．线性表的最基本的四种操作分别是插入、删除、查找和______操作。45．循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针______，而非循环单链表的尾结点指针______。 46．访问单链表中的结点，必须沿着______依次进行。 47．在双向链表中，每个结点有两个指针域，一个指向______，另一个指向______。48．在一个双向链表中删除指针p所指向的结点时，需要对p->next->prior指针域赋值为______。 49．设head为单循环链表L的头结点，则L为空表的条件是______。 50．栈又称为______表，队列又称为______表。 41．log2n 42．顺序存储结构 43．前驱结点 44．排序 45．指向链表头结点，指向空 46．指针域或next域 47．前驱结点，后继结点 48．p->prior 49．head->next=head 50．后进先出，先进先出 51．假设以S和X分别表示进栈和退栈操作，则对输入序列a, b, c ,d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是______。 52．在一个用一维数组a[n]表示的顺序栈中，该栈所含元素的个数最少为______个，最多为______。 53．在一个长度为n的顺序表中的删除第i个元素（0≤i≤n-1），需要向前移动______个元素。 54．一个数据结构在计算机中的表示（映象）称为______。 55．在线性结构和树型结构中，前驱结点和后继结点之间分别存在着______和______的联系。 51．b, c ,e, d, a 52．0，n-1 53．n-i 54．数据的存储结构 55．一对一，一对多 56．每次从无序子表中取出一个元素，然后插入到有序子表中的适当位置，此中排序方法叫做_______排序；每次从无序表中挑选出一个最大或者最小元素，把它交换到有序表的一端，此种方法叫做________排序。 57．如图所示，该二叉树的中序遍历序列是____________。 56．插入，选择57．A B C D E G F 数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） 大数据考试题含答案精 编W O R D版 IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】 1 多选传统大数据质量清洗的特点有： A. 确定性 B. 强类型性 C. 协调式的 D. 非确定性 2 多选以下选项中属于数据的作用的是（）。 A. 沟通 B. 验证假设 C. 建立信心 D. 欣赏 3 多选数据建立信心的作用需具备的条件包括（）。 A. 可靠数据源 B. 多方的数据源 C. 合适的数据分析 D. 信得过的第三方单位 4 多选数据只有在与（）的交互中才能发挥作用。 A. 人 B. 物 C. 消费者 D. 企业 5 单选大数据可能带来（），但未必能够带来（）。 A. 精确度；准确度 B. 准确度；精确度 C. 精确度；多样性 D. 多样性；准确度 6 多选大数据的定义是： A. 指无法在可承受的时间范围内用常规软件工具进行捕捉、管理和处理的数据集合 B. 任何超过了一台计算机处理能力的数据量 C. 技术 D. 商业 7 多选大数据五大类应用方向是： A. 查询 B. 触达 C. 统计 D. 预警 E. 预测 8 多选以下哪些指标是衡量大数据应用成功的标准？ A. 成本更低 B. 质量更高 C. 速度更快 D. 风险更低 9 多选大数据有哪些价值？ A. 用户身份识别 B. 描述价值 C. 实时价值 D. 预测价值 E. 生产数据的价值 10 多选大数据的预测价值体现在： A. 预测用户的偏好、流失 B. 预测热卖品及交易额 C. 预测经营趋势 D. 评价 11 单选什么是大数据使用的最可靠方法？ A. 大数据源 B. 样本数据源 C. 规模大 D. 大数据与样本数据结合 12 多选大数据是描述（）所发生的行为。 A. 未来 B. 现在 C. 过去 D. 实时 13 多选传统研究中数据采集的方法包括： A. 网络监测 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 P175: 5. 设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC，BD→A } 1)求R的所有候选键。 2)求出F的最小函数依赖集Fmin。 3)根据函数依赖关系，确定关系模式R属于第几范式。 4)将R分解为3NF，并保持无损连接性和函数依赖性。 答：1）属性分类为: L类:B,D ; LR类:A,C; R类:无; N类:无 因为（BD）+=ABCD ,所以BD是唯一候选键. 2） ●函数依赖F={A→C, C→A, B→AC, D→AC, BD→A }右部分解为单属性为 F={A→C, C→A, B→A, B→C, D→A, D→C, BD→A } ●因为B+=ABC,所欲BD→A，D为左部多余的属性.将D去掉，则 F={A→C, C→A, B→A, B→C, D→A, D→C } ●冗余函数依赖: 因为B+=ABC,所以B→A多余,去掉. 因为D+=ACD,所以D→A多余,去掉. 所以Fmin={A→C, C→A, B→C, D→C } 4)根据算法4.6，以及Fmin，F中没有X→Y，XY=R的函数依赖，也没有属性在F的函数依赖中左右都无关。所以将Fmin中的各个函数依赖单独构成一个关系模式， 对于Fmin中每一个函数依赖： A→C：表中数据不改变； C→A：将A中所有b给为a1； 表中没有都是a的行，所以不是无损连接的。 因此根据算法 4.7，将候选键作为一个关系模式加入到ρ中，所以结果为ρ={AC,BC,DC，BD} 6.设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC } 1)求（AD）+，B+。 2)求出R 的所有候选键。 3)求出F的最小函数依赖集Fmin。 4)根据函数依赖关系，确定关系模式R属于第几范式。 5)将R分解为3NF，并保持无损连接性和函数依赖性 6)略 答： 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O （nlog2n）。 （19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 大数据时代题目及答案(三套试题仅供参考) 第一套试题 1、当前大数据技术的基础是由（C）首先提出的。（单选题，本题2分） A：微软 B：百度 C：谷歌 D：阿里巴巴 2、大数据的起源是（C ）。（单选题，本题2分） A：金融 B：电信 C：互联网 D：公共管理 3、根据不同的业务需求来建立数据模型，抽取最有意义的向量，决定选取哪种方法的数据分析角色人员是（C）。（单选题，本题2分） A：数据管理人员 B：数据分析员 C：研究科学家 D：软件开发工程师 4、（D ）反映数据的精细化程度，越细化的数据，价值越高。（单选题，本题2分） A：规模 B：活性 C：关联度 D：颗粒度 5、数据清洗的方法不包括（ D）。（单选题，本题2分） A：缺失值处理 B：噪声数据清除 C：一致性检查 D：重复数据记录处理 6、智能健康手环的应用开发，体现了（ D）的数据采集技术的应用。（单选题，本题2分） A：统计报表 B：网络爬虫 C：API接口 D：传感器 7、下列关于数据重组的说法中，错误的是（A）。（单选题，本题2分） A：数据重组是数据的重新生产和重新采集 B：数据重组能够使数据焕发新的光芒 C：数据重组实现的关键在于多源数据融合和数据集成 D：数据重组有利于实现新颖的数据模式创新 8、智慧城市的构建，不包含（ C）。（单选题，本题2分） A：数字城市 B：物联网 C：联网监控 D：云计算 9、大数据的最显著特征是（A）。（单选题，本题2分） A：数据规模大 B：数据类型多样 C：数据处理速度快 D：数据价值密度高10、美国海军军官莫里通过对前人航海日志的分析，绘制了新的航海路线图，标明了大风与洋流可能发生的地点。这体现了大数据分析理念中的（B ）。（单选题，本题2分） A：在数据基础上倾向于全体数据而不是抽样数据 B：在分析方法上更注重相关分析而不是因果分析 C：在分析效果上更追究效率而不是绝对精确 D：在数据规模上强调相对数据而不是绝对数据 11、下列关于舍恩伯格对大数据特点的说法中，错误的是（D）。（单选题，本题2分） A：数据规模大 B：数据类型多样 C：数据处理速度快 D：数据价值密度高12、当前社会中，最为突出的大数据环境是（A）。（单选题，本题2分） A：互联网 B：物联网 C：综合国力 D：自然资源 13、在数据生命周期管理实践中，（ B）是执行方法。（单选题，本题2分） A：数据存储和备份规范 B：数据管理和维护 C：数据价值发觉和利用 D：数据应用开发和管理 14、下列关于网络用户行为的说法中，错误的是（C）。（单选题，本题2分） A：网络公司能够捕捉到用户在其网站上的所有行为 B：用户离散的交互痕迹能够为企业提升服务质量提供参考 C：数字轨迹用完即自动删除 D：用户的隐私安全很难得以规范保护 15、下列关于计算机存储容量单位的说法中，错误的是（ C）。（单选题，本题2分） A：1KB＜1MB＜1GB B：基本单位是字节（Byte） C：一个汉字需要一个字节的存储空间 D：一个字节能够容纳一个英文字符， 16、下列关于聚类挖掘技术的说法中，错误的是（B）。（单选题，本题2分） A：不预先设定数据归类类目，完全根据数据本身性质将数据聚合成不同类别 数据结构（本科）试卷7 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B.较快 C. 相同 二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有____2___个直接前驱（或直 接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_ 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 1. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 一、单项选择题 1.逻辑关系是指数据元素间的（） A．类型 B．存储方式 C．结构 D．数据项 2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构 为( ) A．顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear 为队尾指针，则执行出队操作后其头指针front值为（） A．front=front+1 B．front= (front+1)%(m-1) C．front=(front-1)%m D．front=(fro nt+1)%m 4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队满的条件为( )。 A．rear％n==front B．(front+l)％n==rear C．rear％n-1==front D．(rear+l)％n==front 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别 为队头指针和队尾指针，则判断队空的条件为( )。 A．rear％n==front B．front+l=rear C．rear==front D．(rear+l)％n=front 6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。 ( ) A. 90 B. 91 C. 92 D. 93 7.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利 用（）。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 10.对线性表进行二分查找时，要求线性表必须( )。 第1章绪论 1 ?简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0, ± 1，土2，…}，字母字符数据对象是集合C={ ‘A',‘ B',…，‘ Z', ‘a',‘ $,???,‘ z' }, 学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2?试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元（如用数组表示）来存放 这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3?简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构数据结构考试试题及答案
大数据考试题含答案精编WORD版
数据结构课后习题答案
数据结构DB课后题部分答案
数据结构课后习题及答案
2017年数据结构期末考试题及答案A
《数据结构》课后参考答案
数据结构作业及答案范文
数据结构期末考试题及标准答案
大数据时代题目及答案(三套试题仅供参考)
数据结构试题(附有答案)
《数据结构》期末考试题及答案
武汉大学数据结构考试题(附答案)
严蔚敏版数据结构课后习题答案-完整版
2015年数据结构期末考试题及答案
数据结构练习附答案
(完整版)数据结构课后答案
相关主题
文本预览