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

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

密 2009-2010-1学期

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

考试科目：数据结构_本

年级 层次 教学班 姓名： 学号：

1、本次考试为卷考试，考试时间分钟。

2、请将答案依次写在专用 上。

3

一、单项选择题（共15题，每题2分，共计30分）

1、算法指的是（ ）。

A、计算机程序 B、解决问题的计算方法

C、排序算法 D、解决问题的有限运算序列

2、若进栈序列为1、2、3、4、5，若允许出栈操作可以在任意可能的时刻进行，则以下不可能的出栈序列是（ ）。

A、3、4、2、5、1 B、2、5、4、1、3

C、2、3、1、5、4 D、3、5、4、2、1

3、在一个长度为n的顺序表中向第i个元素(0<i<n+1)之前插入一个新元素时，需要向后移动（ ）个元素。

A、n-i B、n-i+1 C、n-i-1 D、i

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、线索二叉树中，结点p没有左子数的充要条件是（ ）。

A、p->lc=NULL B、p->ltag=1

C、p->lc=NULL且p->ltag=1 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、线性表采用链式存储时，其元素地址（ ）。

A、必须是连续的 B、一定是不连续的 C、部分地址是连续的 D、连续与否均可

11、对一组数据（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、插入

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

12、在数据结构中，从逻辑上可以把数据结构分为（ ）。

A．动态结构和静态结构 B. 紧凑结构和非紧凑结构

C. 线性结构和非线性结构 D. 内部结构和外部结构

13、已知函数SubString(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数SCopy(s,t)的功能为复制串t到s。若字符串S=”SCIENCESTUDY”，则调用函数SCopy(P,Sub(S,1,7))后得到（ ）。

A、P=”SCIENCE” B、P=”STUDY” C、S=”SCIENCE” D、S=”STUDY”

14、若将一个10×10阶的对称矩阵压缩存储到一个一维数组中，则该一维数组的大小应该是（ ）。

A、55 B、56 C、45 D、46

15、根据堆定义，下面的4个序列中，（ ）是堆。

A、75，65，30，15，25，45，20，10

B、75，65，45，10，30，25，20，15

C、75，45，65，30，15，25，20，10

D、75，45，65，10，25，30，20，15

二、是非题（下列叙述正确的写上T，否则，写上F。共10题，每题1分，共计10分）

1、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。

（ ）

2、线性表中的每个结点最多只有一个前驱和一个后继。（ ）

3、线性表简称为“顺序表”。（ ）

4、线性的数据结构可以顺序存储，也可以链式存储。非线性的数据结构只能连接存储。（ ）

5、从单链表的任一结点出发，都能访问到所有结点。（ ）

6、满二叉树一定是完全二叉树。（ ）

7、在有向图G中，<V2,V1>和<V1,V2>是两条不同的边。（ ）

8、在有序的顺序表和有序的链表上，均可使用折半查找来提高查找效率。（ ）

9、若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定是任何结点都没有右子树。（ ）

10、如果某种排序方法是不稳定的，那么该排序方法不具有实用价值。（ ）

三、填空题（共10空，每空1分，共计10分）

1、每次从无序表中顺序取出一个元素，把这个元素插入到有序表中的适当位置，此种排序方法叫做

【1】 排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 【2】 排序。

2、如果经常对线性表进行插入和删除运算，则最好采用存储结构。

3、数据结构按结点间的关系，可分为4中逻辑结构，它们分别是、。

4、假定一个顺序循环队列的存储空间长度为QueueSize，队首和队尾指针分别用front和rear表示，如果采用少用一个存储空间的方式来区分循环队列是队空还是队满，则判断队空的条件是 【8】 。

5、已知二维数组A[5][3]，其每个元素占2个存储单元，并且A[0][0]的存储地址为1000。则元素A[3][2]的存储地址为

四、算法填空题（每空2分，共20分）

1、下列算法片段是矩阵快速转置算法，请在划线的位置填入适当的内容。

#define ARRAYSIZE 1024

typedef struct{

int row,col; /*非零元素的行号和列号*/

DataType value; /*非零元素的值*/

}TriType;

typedef struct{

triType items[ARRAYSIZE+1]; /*非零元三元组，item[0]未用*/

int rows,cols; /*稀疏矩阵的行数、列数*/

int nums; /*稀疏矩阵的非零元素个数*/

}TriArray;

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

FastTransMatrix(TriArray TA, TriArray TB)

{/*TA为转置前的三元组属性表，TB为转置后的三元组顺序表*/

int i, j=0, k=0;

int pos[ARRATSIZE+1], num[ARRATSIZE+1];

if(TA.nums)

{

for(i=1;i<=TA.cols;i++) num[i]=0;

for(i=1;i<=TA.nums;i++) /*求TA中每一列非零元个数*/

;

pos[1]=1;

for(i=2;i<=TA.cols;i++) /*计算第i列第一个非零元的位置

;

for(i=1;i<=TA.nums;i++)

{

j=TA.items[i].col;

k=pos[j];

TB.items[k].row=TA.items[i].col;

TB.items[k].col=TA.item[i].row;

TB.items[k].value=TA.items[i].value;

}

}

TB.rows=TA.col …… 此处隐藏：2584字，全部文档内容请下载后查看。喜欢就下载吧 ……