西南财经大学天府学院试卷(B卷)

西南财经大学天府学院试卷(B卷) 考试科目：数据结构_本 年级 　 层次 　 教学班 姓名： 学号： 记 分 表 试题号 一 二 三 四 五 六 总分 考分 阅卷人 注意： 1、本次考试为A卷考试，考试时间120分钟。 2、请将答案依次写在专用 答题纸 上。 3、全卷共一部分，满分为100分。 一、单项选择题（共15题，每题2分，共计30分） 1、在数据结构学科中，伪代码是（ ） A、描述算法且容易理解的一种语言 B、能够方便描述算法中的分支与循环等结构化语句 C、不能直接编译或解释执行 D、以上都正确 2、若进栈序列为1、2、3、4，进栈过程中可以出栈，则以下不可能的出栈序列是（） A、1、4、3、2 B、2、3、4、1 C、3、1、4、2 D、3、4、2、1 3、设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i<=n; i++) for(j=1; j<=n; j++) x++; A、O(1) B、O(n2) C、O(n) D、O(n3) data next 4、假定一个链表队列的队首和队尾指针分别用front和rear表示，每个结点的结构为：当出队时所进行的指针操作为（） A、front = front–> next B、rear = rear–>next C、front–>next = rear ; rear = rear–>next D、front = front–>next ; front–>next = rear 5、向一个栈顶指针为hs的链栈中插入一个s 结点时，应执行（ ）。 A、hs->next=s; B、s->next=hs; hs=s; C、s->next=hs->next; hs->next=s; D、s->next=hs; hs=hs->next; 6、对于顺序存储的有序表 {5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数为（ ）。 A、2 B、3 C、4 D、5 7、对一组数据（86，48，26，15，23）排序，数据的排列次序在排序过程中的变化为： ① 86 48 26 15 23 ② 15 48 26 86 23 ③ 15 23 26 86 48 ④ 15 23 26 48 86 这个排序过程采用的排序方法是（ ）。 A、冒泡 B、选择 C、快速 D、插入 8、 若根据查找表（23，44，36，48，52，73，64，58）建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数为（ ）。 A、1 B、2 C、3 D、4 9、若一个元素序列基本有序，则选用（ ）方法较快。 A、直接插入排序 B、简单选择排序 C、堆排序 D、快速排序 10、在一个长度为n的顺序表中向第i个元素(0lc=NULL B、p->ltag=1 C、p->lc=NULL且p->ltag=1 D、以上都不对 二、是非题（下列叙述正确的写上T，否则，写上F。共10题，每题1分，共计10分） 1、在有向图G中，和是两条不同的边。（ ） 2、线性表中的每个结点最多只有一个前驱和一个后继。（ ） 3、线性表简称为“顺序表”。（ ） 4、线性的数据结构可以顺序存储，也可以链式存储。非线性的数据结构只能连接存储。（ ） 5、从单链表的任一结点出发，都能访问到所有结点。（ ） 6、在有序的顺序表和有序的链表上，均可使用折半查找来提高查找效率。（ ） 7、如果某种排序方法是不稳定的，那么该排序方法不具有实用价值。（ ） 8、满二叉树一定是完全二叉树。（ ） 9、若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定是任何结点都没有右子树。（ ） 10、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 （ ） 三、填空题（共10空，每空1分，共计10分） 1、队列和堆栈最大的相同点在于，它们都同属于 【1】 ;队列和栈最大的不同点在于，队列元素的删除和插入遵循 【2】 规则；而栈元素的删除和插入遵循后进先出（LIFO）规则。 2、如果经常对线性表进行插入和删除运算，则最好采用 【3】 存储结构。 3、已知二维数组A[5][3]，其每个元素占2个存储单元，并且A[0][0]的存储地址为1000。则元素A[3][2]的存储地址为 【4】 。 4、假定一个顺序循环队列的存储空间长度为QueueSize，队首和队尾指针分别用front和rear表示，如果采用少用一个存储空间的方式来区分循环队列是队空还是队满，则判断队空的条件是 【5】；判断队满的条件是 【6】 。 5、数据结构按结点间的关系，可分为4中逻辑结构，它们分别是 【7】 、 【8】 、 【9】 和 【10】 。 四、算法填空题（每空2分，共20分） 1、已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode{ ElemType data; BinTreeNode *left,*right; }; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在画有横线的地方填写合适内容。 int NodeLevel(BinTreeNode *BT,ElemType X) { int c1,c2; if(BT==NULL) return 0; /*空树的层号为0*/ else if(BT->data == X) return 1; /*根结点的层号为1*/ else { c1=NodeLevel(BT->left,X) if(c1>=1) return c1+1; c2= 【1】 ; if ( 【2】 ) return 【3】 ; else return 0; /*若树中不存在X结点则返回0*/ } } 2、下列算法片段是矩阵快速转置算法，请在划线的位置填入适当的内容。 #define ARRAYSIZE 1024 typedef struct{ int row,col; /*非零元素的行号和列号*/ DataType valu