机密★启用前
大连理工大学网络教育学院
2016年9月《数据结构》课程
期末复习资料
☆ 注意事项：本复习题满分共：400分。
一、单项选择题（本大题共65小题，每小题3分，共195分）
1．对于一个算法，当输入非法数据时，也要能作出相应得处理，这种要求称为（ ）。 (A)、正确性 (B)、 可行性 (C)、 健壮性 (D)、 输入性
2．设S为C语言得语句,计算机执行下面算法时，算法得时间复杂度为（ ）。
for(i=n-1；i>=0；i--)
for(j=0；j （A）、有序顺序表 （B）、有序单链表 （C）、有序顺序表与有序单链表都可以 （D）、无限制 4．顺序存储结构得优势就是（ ）。 （A）、利于插入操作 （B）、利于删除操作 （C）、利于顺序访问 （D）、利于随机访问 5．深度为k得完全二叉树，其叶子结点必在第（ ）层上。 （A）、k-1 （B）、k （C）、k-1与k （D）、1至k 6．具有60个结点得二叉树，其叶子结点有12个，则度为1得结点数为（ ） （A）、11 （B）、13 （C）、48 （D）、37 7、下列程序段得时间复杂度为（）。 for(i=0； i for(i=0； i 9．设F就是由T1、T2与T3三棵树组成得森林，与F对应得二叉树为B，T1、T2与T3得结点数分别为N1、N2与N3，则二叉树B得根结点得左子树得结点数为（）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 10．利用直接插入排序法得思想建立一个有序线性表得时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n) 11．设指针变量p指向双向链表中结点A，指针变量s指向被插入得结点X，则在结点A得后面插入结点X得操作序列为（）。 (A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s； 12．图得Depth-First Search(DFS)遍历思想实际上就是二叉树（ ）遍历方法得推广。 2 2 （A）、先序 （B）、中序 （C）、后序 （D）、层序 13．在上图列链队列Q中，元素a出队得操作序列为（ ） （A）、p=Q、front->next; p->next= Q、front->next; （B）、p=Q、front->next; Q、front->next=p->next; （C）、p=Q、rear->next; p->next= Q、rear->next; （D）、p=Q->next; Q->next=p->next; 14． Huffman树得带权路径长度WPL等于（ ） （A）、除根结点之外得所有结点权值之与 （B）、所有结点权值之与 （C）、各叶子结点得带权路径长度之与 （D）、根结点得值 15．线索二叉链表就是利用（ ）域存储后继结点得地址。 （A）、lchild （B）、data （C）、rchild （D）、root 16．组成数据得基本单位就是（ ）。 (A) 数据项 (B) 数据类型 <4，1>}，则数据结构A就是（ ）。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 18．数组得逻辑结构不同于下列（ ）得逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 19．二叉树中第i(i≥1)层上得结点数最多有（ ）个。 A．2i B．2i+1 C．2i-1 20、 对一个算法得评价，不包括如下（ ）方面得内容。 A．健壮性与可读性 B．并行性 C．正确性 D．时空复杂度 21、 在带有头结点得单链表HL中，要向表头插入一个由指针p指向得结点，则执行( )。 A、 p->next=HL->next; HL->next=p; B、 p->next=HL; HL=p; C、 p->next=HL; p=HL; D、 HL=p; p->next=HL; 22、 对线性表，在下列哪种情况下应当采用链表表示？( ) A、经常需要随机地存取元素 B、经常需要进行插入与删除操作 C、表中元素需要占据一片连续得存储空间 D、表中元素得个数不变 23、一个栈得输入序列为1 2 3，则下列序列中不可能就是栈得输出序列得就是( ) A、 2 3 1 B、 3 2 1 C、 3 1 2 D、 1 2 3 24．下列各种排序算法中平均时间复杂度为O(n2)就是（）。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序 25．设输入序列1、2、3、…、n经过栈作用后，输出序列中得第一个元素就是n，则输出序列中得第i个输出元素就是（）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 26．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 (A) 小于等于m得最大奇数 (B) 小于等于m得最大素数 (C) 小于等于m得最大偶数 (D) 小于等于m得最大合数 (D) 树 D．2i+2 (C) 数据元素 (D) 数据变量 17．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>， 27．设在一棵度数为3得树中，度数为3得结点数有2个，度数为2得结点数有1个，度数为1得结点数有2个，那么度数为0得结点数有（）个。 (A) 4 (B) 5 (C) 6 (D) 7 28．设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 29． AOV网就是一种（ ）。 A．有向图 B．无向图 C．无向无环图 D．有向无环图 30．采用开放定址法处理散列表得冲突时，其平均查找长度（ ）。 A．低于链接法处理冲突 B、 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 31．若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 A．值 B．函数 C．指针 D．引用 32．在稀疏矩阵得带行指针向量得链接存储中，每个单链表中得结点都具有相同得（ ）。 A．行号 B．列号 C．元素值 D．非零元素个数 33．快速排序在最坏情况下得时间复杂度为（ ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 34．从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2) 35．设指针变量p指向单链表结点A，则删除结点A得后继结点B需要得操作为（ ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 36．设栈S与队列Q得初始状态为空，元素E1、E2、E3、E4、E5与E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列得顺序为E2、E4、E3、E6、E5与E1，则栈S得容量至少应该就是（ ）。 (A) 6 (B) 4 (C) 3 (D) 2 37．将10阶对称矩阵压缩存储到一维数组A中，则数组A得长度最少为（ ）。 (A) 100 (B) 40 (C) 55 (D) 80 38．设结点A有3个兄弟结点且结点B为结点A得双亲结点，则结点B得度数数为（ ）。 (A) 3 (B) 4 (C) 5 (D) 1 39．根据二叉树得定义，可知具有3个结点得二叉树共有（ ）种不同得形态。 (A) 4 (B) 5 (C) 6 (D) 7 40、 设有以下四种排序方法，则（ ）得空间复杂度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序 41．设某无向图有n个顶点，则该无向图得邻接表中有（ ）个顶点头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 42．设无向图G中有n个顶点，则该无向图得最小生成树上有（）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 43．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到得一趟快速排序结果就是（）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 44．（）二叉排序树可以得到一个从小到大得有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历 45．设按照从上到下、从左到右得顺序从1开始对完全二叉树进行顺序编号，则编号为i结点得左孩子结点得编号为（）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 46．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；得时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 47．设带有头结点得单向循环链表得头指针变量为head，则其判空条件就是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 48．设某棵二叉树得高度为10，则该二叉树上叶子结点最多有（）。 (A) 20 (B) 256 (C) 512 (D) 1024 49．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较得关键字个数为（）。 (A) 1 (B) 2 (C) 3 (D) 4 50．设指针变量top指向当前链式栈得栈顶，则删除栈顶元素得操作序列为（）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 51．栈与队列得共同特点就是( )。 A、只允许在端点处插入与删除元素 B、都就是先进后出 C、都就是先进先出 D、没有共同点 52．用链接方式存储得队列，在进行插入运算时( )、 A、 仅修改头指针 B、 头、尾指针都要修改 C、 仅修改尾指针 D、头、尾指针可能都要修改 53．以下数据结构中哪一个就是非线性结构？( ) A、 队列 B、 栈 C、 线性表 D、 二叉树 54．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 55．树最适合用来表示( )。 A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系得数据 D、元素之间无联系得数据 56．设顺序表得长度为n，则顺序查找得平均比较次数为（）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 57．设有序表中得元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24得元素需要经过（）次比较。 (A) 1 (B) 2 (C) 3 (D) 4 58．设顺序线性表得长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。 (A) 6 (B) 11 (C) 5 (D) 6、5 59．设有向无环图G中得有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G得一种拓扑排序序列得就是（）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 60．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成得二叉排序树得深度为（）。 (A) 4 (B) 5 (C) 6 (D) 7 61 ．二叉树得第k层得结点数最多为( )、 A．2 B、 2 C、 2 D、 2查找，则查找A［3］得比较序列得下标依次为( ) A、 1，2，3 C、 9，5，3 B、 9，5，2，3 D、 9，4，2，3 k k-2 k+1 k-1 62 ．若有18个元素得有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分 63．对n个记录得文件进行快速排序，所需要得辅助存储空间大致为 A、 O（1） B、 O（n） C、 O（1og2n） D、 O（n2） 64 ．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1得元素有（ ）个， A．1 B．2 C．3 D．4 65．设有6个结点得无向图，该图至少应有( )条边才能确保就是一个连通图。 A、5 B、6 C、7 D、8 二、填空题（本大题共40小题，每小题2分，共80分） 1、 设指针变量p指向双向链表中得结点A，指针变量s指向被插入得结点X，则在结点A得后面插入结点X得操作序列为_________=p；s->right=p->right；p->right->left=s；__________=s；（设结点中得两个指针域分别为left与right）。 2、 设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。 3、 当用长度为N得数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满得条件就是_____________________。 4、 对于一个长度为n得单链存储得线性表，在表头插入元素得时间复杂度为_________，在表尾插入元素得时间复杂度为____________。 5、 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W得数据元素共占用＿_____＿个字节。W中第6 行得元素与第4 列得元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6][3]得起始地址为＿________＿。 6、 广义表A= (a,(a,b),((a,b),c)),则它得深度为____________，它得长度为____________。 7、 二叉树就是指度为2得____________________树。一棵结点数为N得二叉树，其所有结点得度得总与就是_____________。 8、 设有一组初始关键字序列为(24，35，12，27，18，26)，按照从小到大排序，则第3趟直接插入排序结束后得结果得就是__________________________________。 9、 设一棵二叉树得前序序列为ABC，则有______________种不同得二叉树可以得到这种序列。 10、 下面程序段得功能就是实现一趟快速排序，请在下划线处填上正确得语句。 struct record {int key;datatype others;}; void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(i while (i
大工16春《数据结构》开卷考试复习
