当前位置:文档之家› 2011广西壮族自治区数据结构考试加强

2011广西壮族自治区数据结构考试加强

2011广西壮族自治区数据结构考试加强
2011广西壮族自治区数据结构考试加强

1、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。

void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数

node edge[];

scanf( "%d%d",&e,&n) ; //输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边:顶点,权值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。

{edge[0]=edge[i]; j=i-1;

while (edge[j].w

edge[j+1]=edge[0]; }//for

k=1; eg=e;

while (eg>=n) //破圈,直到边数e=n-1.

{if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除k++; //下条边

}//while

}//算法结束。

connect()是测试图是否连通的函数,可用图的遍历实现,

2、数组A和B的元素分别有序,欲将两数组合并到C数组,使C仍有序,应将A和B拷贝到C,只要注意A和B数组指针的使用,以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。

void union(int A[],B[],C[],m,n)

//整型数组A和B各有m和n个元素,前者递增有序,后者递减有序,本算法将A和B归并为递增有序的数组C。

{i=0; j=n-1; k=0;// i,j,k分别是数组A,B和C的下标,因用C描述,下标从0开始while(i=0)

if(a[i]

while(i

while(j>=0) c[k++]=b[j--];

}算法结束

4、要求二叉树按二叉链表形式存储。15分

(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() //建立二叉树的二叉链表形式的存储结构

{ElemType x;BiTree bt;

scanf(“%d”,&x); //本题假定结点数据域为整型

if(x==0) bt=null;

else if(x>0)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt->data=x; bt->lchild=creat(); bt->rchild=creat();

}

else error(“输入错误”);

return(bt);

}//结束 BiTree

int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0

{int tag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量足够大

if(p==null) return (1);

QueueInit(Q); QueueIn(Q,p); //初始化队列,根结点指针入队

while (!QueueEmpty(Q))

{p=QueueOut(Q); //出队

if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队

else {if (p->lchild) return 0; //前边已有结点为空,本结点不空

else tag=1; //首次出现结点为空

if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队

else if (p->rchild) return 0; else tag=1;

} //while

return 1; } //JudgeComplete

3、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数

{if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大

int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数

int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数

while(front<=rear)

{p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点

if(p->lchild) Q[++rear]=p->lchild; //左子女入队

if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1

last=rear; } //last移到指向下层最右一元素

if(level>k) return (leaf); //层数大于k 后退出运行

}//while }//结束LeafKLevel

4、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。

5、约瑟夫环问题(Josephus问题)是指编号为1、2、…,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,…,如此重复直到所有的人全部出列为止。现要

求采用循环链表结构设计一个算法,模拟此过程。

#include

typedef int datatype;

typedef struct node

{datatype data;

struct node *next;

}listnode;

typedef listnode *linklist;

void jose(linklist head,int s,int m)

{linklist k1,pre,p;

int count=1;

pre=NULL;

k1=head; /*k1为报数的起点*/

while (count!=s) /*找初始报数起点*/

{pre=k1;

k1=k1->next;

count++;

}

while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/ { p=k1; /*从k1开始报数*/

count=1;

while (count!=m) /*连续数m个结点*/

{ pre=p;

p=p->next;

count++;

}

pre->next=p->next; /*输出该结点,并删除该结点*/

printf("%4d",p->data);

free(p);

k1=pre->next; /*新的报数起点*/

}

printf("%4d",k1->data); /*输出最后一个结点*/

free(k1);

}

main()

{linklist head,p,r;

int n,s,m,i;

printf("n=");

scanf("%d",&n);

printf("s=");

scanf("%d",&s);

printf("m=",&m);

scanf("%d",&m);

if (n<1) printf("n<0");

else

{/*建表*/

head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/

head->data=n;

r=head;

for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/

{ p=(linklist)malloc(sizeof(listnode));

p->data=i;

p->next=head;

head=p;

}

r->next=head; /*生成循环链表*/

jose(head,s,m); /*调用函数*/

}

}

6、冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。

48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)

7、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树结点指针,l中保留当前最长路径中的结点

int i,top=0,tag[],longest=0;

while(p || top>0)

{ while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下

if(tag[top]==1) //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看路径长度

if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈,记住最高栈顶指针,退栈

}

else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下

}//while(p!=null||top>0)

}//结束LongestPath

2010年数据结构期中考试试卷及答案

《数据结构》期中试卷(2009级) 2010-2011学年第一学期姓名:学号:成绩: 一、选择题:(每小题2分,共20分) 1.有六个元素6,5,4,3,2,1 的顺序进栈,下列哪一个不是合法的出栈序列?() A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动() 个元素。 A.8 B. 62.5 C. 62 D. 7 3. 已知广义表A=((a,b,c),(d,e,f),(h,(i,j)),g),从A表中取出原子项e的运算是:( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中,设front和rear分别为队列的头指针和尾指针,则入队 时的操作为()。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指 针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A.p->llink=q; q->rlink=p;p->llink->rlink=q;q->llink=q; B.p->llink=q;p->llink->rlink=q ;q->rlink= p;q->llink=p->llink; C.q->rlink=p;q->llink=p->llink;p->llink->rlink=q; p->llink=q; D.q->llink=p->llink;q->rlink=p;p->llink=q;p->llink=q; 6. 一棵完全二叉树上有1001个结点,其中叶子结点的个数是()。 A.250 B.500 C.254 D.以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果 为()。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 8. 利用二叉链表存储树时,则根结点的右指针是()。 A.指向最左孩子B.指向最右孩子C.空D.非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节,第一个元素的存储地址为100, 若按列优先顺序存储,则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是() A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一

数据结构试题(附有答案)

数据结构(本科)试卷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中第_

华师大数据结构期中考试试卷(含答案)

华东师范大学期中试卷 2007—2008学年第二学期 课程名称:______数据结构_____ 姓名:___________________ 学号:__________________ 专业:___________________ 年级/班级:__________________ 课程性质:专业必修 一、单项选择题(共18分,每题3分) 1. Stack has the property called last in and first out, then which of the following describes the property of Queue a) Last in and first out b) First in and last out c) First in and first out 2. A list of items from which only the item most recently added can be removed is known as a ( ) a) stack b) queue c) circular linked list d) list 3. If the following function is called with a value of 2 for n, what is the resulting output void Quiz( int n ) { if (n > 0) { cout << 0; Quiz(n - 1); cout << 1; Quiz(n - 1); } }

a) 00011011 b) c) d) 01100011 e) 001101 4. A heap is a list in which each entry contains a key, and, for all positions i in the list, the key at position i is at lease as large as the keys in positions 2i+2 and ( ), provided these positions exist in the list. a) 2i b) 2i-1 c) 2i-2 d) 2i+1 5. Given the recursive function int Func( /* in */ int i, /* in */ int j ) { if (i < 11) if (j < 11) return i + j; else return j + Func(i, j - 2); else return i + Func(i - 1, j); } what is the value of the expression Func(12, 15) a) 81 b) 62 c) 19 d) 72 e) none of the above 6. Shell sort finally perform an ordinary ( ) a) Heap sort b) Insertion sort c) Selection sort d) Quick sort 二、填空题(共22分,每空2分) 1. If the following function is called with a value of 75 for n, the resulting output is

数据结构试题及答案(免费)

一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表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; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度()。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的()。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为()。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。

数据结构期中考试试题答案c语言版本

数据结构期中考试试题答案 一、单选题(每小题2分,共8分) 1.在一个长度为n的线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x同元素的平均比较次数,假定查找每个元素的概率都相等)为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.在一个带附加表头的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行 D 。 A.HL=p;p->next=HL; B.p->next=HL;HL=p; C.p->next=HL;p=HL; D.p->next=HL->next;HL ->next=p; 3.若让元素A,B,C,D依次入栈,则出栈次序不可能出现 D 种情况。 A.D,C,B,A B.A,D,C,B C.B,A,D,C D.D,A,B,C 4.从一个顺序队列删除元素时,首先需要 B 。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 二、填空题(每空1分,共32分) 1.数据的逻辑结构分为集合、线性、树型、图形四种。 2.函数重载要求参数个数、参数类型或参数次序有所不同。 3.在带附加表头的循环双向链表中,表头附加结点的左指针域指向最后一个结点,最后一个结点的右指针域指向表头附加结点。

4.在以HL为表头指针的带附加结点的单链表和循环单链表中,链表为空的条件分别为 HL->next==NULL 和 HL==HL->next 。 5.在由数组a中元素结点构成的单链表中,删除下标为i的结点后,需要把该结点插入到空闲表的表头,具体操作为 a[i].next=a[1].next 、a[1].next=i 。 6.在由数组a中元素结点构成的单链表中,删除下标为i的结点的后继结点并将被删除结点的下标赋给i时,所进行的操作(需要用一个临时变量p)描述为 p=a[i].next 和 a[i].next=a[p].next;i=p 。 7.在稀疏矩阵的十字链接存储中,每个结点的down指针域指向列 号相同的下一个结点,right指针域指向行号相同的下一个结点。 8.一个广义表中的元素分为单元素和表元素两类。 9.广义表A=((a,(b,(),c),((d),e)))的长度为 1 ,深度为 4 。 10.向一个顺序栈插入一个元素时,首先应 top++ ,然后再将待插入元素放入栈顶位置。 11.对于队列,应在队尾进行插入,在队首进行删除。 12.中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @ 。 13.后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 3 。 14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 a ,孩子结点为 f ,树的深度为 4 。 三、运算题(每小题8分,共24分) 1.假定线性表L=(33,69,78,22,44,88),i=3,x=34,y=22,则对L进行下列一组操作` ListEmpty(L); false GetElem(L,i); 78

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (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)下列程序得时间复杂度为() i=0;s=0; while(s

《数据结构》期末考试试卷

广东创新科技职业学院期末考试试题(标明A 卷、B 或C 卷) 2018 —2019 学年第二学期考试科目:《数据结构》 (闭(开)卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题(每小题 2 分,共 40 分) 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. 下述程序段①中各语句执行频度的和是()。 s=0; ① for(i=1;i<=i;j++) s+=j; A .n-1 B .n C .2n-1 D .2n 7. 下面程序段的时间复杂度为()。 for(i=0;i

数据结构试题(含答案)

数据结构试题(含答案) 1.数据逻辑结构包括线性结构、树形结构和图状结构三种类型,树形结构和图状结构合称非线性结构 2.数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有 1 个后续结点。 4.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 5.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;叶子结点没. 6.数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点,其余每个结点的后续结点可以任意多个。 7.衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8.评估一个算法的优劣,通常从时间复杂度和空间复杂度两个方面考察。 9.算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 11.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 12.在双链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。13.在顺序表中插入或删除一个数据元素,需要平均移动 n 个数据元素,移动数据元素的个数与位置有关 14.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表的元素是,应采用顺序存储结构 15.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单链表和双链表。 16.顺序存储结构是通过下标表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的 17.带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18.栈是限定仅在表尾进行插入或删除操作的线性表,其运算遵循后进先出的原则。19.空串是零个字符的串,其长度等于零。空白串是由一个或多个空格字符组成的串,其长度等于其包含的空格个数。 20.组成串的数据元素只能是单个字符。 21.一个子串”str”在主串”datastructure”中的位置是 5 。 22.字符串中任意个连续字符构成的部分称为该串的子串。 23.二维数组M的每个元素是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要 540个字节;M的第8列和第5行共占108个字节24.稀疏矩阵一般的压缩存储方法有两种,即三元组表和十字链表。 25.广义表((a),((b),c),(((d))))的长度是 3 ,深度是 4 。 26.在一棵二叉树中,度为零的结点的个数为n0,度为2 的结点的个数为n2,则有n0= n2+1 。 27.在有n个结点的二叉链表中,空链域的个数为__n+1__。 28.一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29.深度为5的二叉树至多有 31 个结点。 30.若某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点个数为69 。

《数据结构》习题汇编08 第八章 查找 试题

数据结构课程(本科)第七章试题 一、单项选择题 1.若搜索每一个元素的概率相等,则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为 ()。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对长度为10的顺序表进行搜索,若搜索前面5个元素的概率相同,均为1/8,搜索后面5个元素的概 率相同,均为3/40,则搜索到表中任一元素的平均搜索长度为()。 A. 5.5 B. 5 C. 39/8 D. 19/4 3.对长度为3的顺序表进行搜索,若搜索第一个元素的概率为1/2,搜索第二个元素的概率为1/3,搜索 第三个元素的概率为1/6,则搜索到表中任一元素的平均搜索长度为()。 A. 5/3 B. 2 C. 7/3 D. 4/3 4.对长度为n的有序单链表,若搜索每个元素的概率相等,则顺序搜索到表中任一元素的平均搜索长度 为()。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 5.对于长度为n的有序顺序表,若采用折半搜索,则对所有元素的搜索长度中最大的为()的值 的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 6.对于长度为n的有序顺序表,若采用折半搜索,则对所有元素的搜索长度中最大的为()的值 的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 7.对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为() 的值除以9。 A. 20 B. 18 C. 25 D. 22 8.对于长度为18的有序顺序表,若采用折半搜索,则搜索第15个元素的搜索长度为()。 A. 3 B. 4 C. 5 D. 6 9.对具有n个元素的有序顺序表进行折半搜索,则搜索任一元素的时间复杂度为()。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中,搜索所有元素的搜索长度中最大的为()。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时,在等概率情况下进行成功搜索的时间复杂度大致为 ()。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

数据结构试题及答案

数据结构试题? 一、?单选题(每题 2 分,共20分) 1.1.???? 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2.???? 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行( A )。 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; 3.3.???? 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时,其平均查找长度( B )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7.???? 若需要利用形参直接访问实参时,应将形参变量说明为( D )参数。 A.值 B.函数 C.指针 D.引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有 相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N(M: N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为

数据结构期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( c)。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为(d )。 for(i=n-1;i>=0;i--) for(j=0;jnext; 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; 9. Huffman树的带权路径长度WPL等于( c ) (A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和 (C)、各叶子结点的带权路径长度之和(D)、根结点的值

数据结构试题及答案

一、判断题: 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。() 8、线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。() 9、栈和队列逻辑上都是线性表。() 10、单链表从任何一个结点出发,都能访问到所有结点() 11、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。() 12、快速排序是排序算法中最快的一种。() 13、多维数组是向量的推广。() 14、一般树和二叉树的结点数目都可以为0。() 15、直接选择排序是一种不稳定的排序方法。() 16、98、对一个堆按层次遍历,不一定能得到一个有序序列。() 17、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。() 18、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。() 19、堆栈在数据中的存储原则是先进先出。() 20、队列在数据中的存储原则是后进先出。() 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。() 22、哈夫曼树一定是满二叉树。() 23、程序是用计算机语言表述的算法。() 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。() 25、用一组地址连续的存储单元存放的元素一定构成线性表。() 26、堆栈、队列和数组的逻辑结构都是线性表结构。() 27、给定一组权值,可以唯一构造出一棵哈夫曼树。() 28、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()

2008年10月份全国自考数据结构真题及答案

更多优质自考资料尽在百度贴吧自考乐园俱乐部 (https://www.doczj.com/doc/fb5176503.html,/club/5346389)欢迎?加入...欢迎?交流...止不住的惊喜等着你......... 2008年10月份全国自考数据结构真题 一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项 中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均 无分。 1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结 构是() A.栈 B.队列 C.树 D.图 答案:C 2.下面程序段的时间复杂度为() A. A B.B C.C D.D 答案:C 3.在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是() A.p->next==head B.p->next->next==head C.p->next==NULL D.p==head 答案:A 4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是() A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 答案:D 5.两个字符串相等的条件是() A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同 答案:D 6. A. A B.B C.C D.D 答案:A 7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为() A.0 B.1 C.48 D.49 答案:D 8.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout ,则所有顶点的入度之和为 ()A.A B.B C. C D.D 答案:A 9.如图所示的有向无环图可以得到的拓扑序列的个数是() A. 3

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为()、()、()和()。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。

数据结构试题及答案

数据结构试卷(十一) 一、选择题(30分) 1.设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2.设无向图G中有n个顶点,则该无向图的最小生成树上有()条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是()。 (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 4.()二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历 5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为()。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为()。 7.设带有头结点的单向循环链表的头指针变23 (A) O(n) (B) O(nlogn) (C) O(n) (D) O(n/2)2 量为head,则其判空条件是()。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有()。 (A) 20 (B) 256 (C) 512 (D) 1024 9.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为()。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为()。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。()2.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。() 3.设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(logn)。()24.完全二叉树中的叶子结点只可能在最后两层中出现。() 5.哈夫曼树中没有度数为1的结点。() 6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。() 7.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()

福建农林大学数据结构考试试卷1

福建农林大学考试试卷(A)卷 2007——2008 学年第二学期 课程名称:数据结构考试时间120分钟 专业年级班学号姓名 一、单项选择题(本大题共10小题,每小题2分,共20分) 1. 顺序栈中压入元素时,是()。 A)先存入元素后移动指针B)先移动指针后存入元素 C)无所谓谁先谁后D)同时进行 2. 线性表的顺序存储结构是一种()的存储结构。 A) 随机存取B) 顺序存取C) 索引存取D) HASH存取 3.若一个栈的输入序列是1,2,3…n,输出序列的第一个元素是n,则第i个输出元素是()。 A)不确定B)n-i C)n-i+1 D)i 4. 在以下的叙述中,正确的是()。 A) 线性表的线性存储结构优于链表存储结构 B) 二维数组是它的每个数据元素为一个线性表的线性表 C) 栈的操作方式是先进先出D) 队列的操作方式是先进后出 5.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()。 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 6. 树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论()是正确的。 A) 树的先根遍历序列与其对应的二叉树的后序遍历序列相同 B) 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C) 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D) 树的后根遍历序列与其对应的二叉树的中序遍历序列相同 7.时间复杂度均为O(nlog2n)且不稳定的排序方法是()。 A)快速排序B)选择排序C)归并排序D)冒泡排序

数据结构期中考试模试卷

数据结构模拟试卷 一. 单选题(每题1分,共14分) 1.数据结构所讨论的基本数据单位是(B)。 A、数据对象 B、数据元素 C、数据项 D、数据类 2. 在数据结构的讨论中把数据结构从逻辑上分为(C)两大类。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构。 3.若一个算法的时间复杂度用T(n)表示,其中n的含义是( A )A.问题规模B.指令条数 C.循环层数D.函数数量 4. 算法分析的目的是(C)。 A. 研究算法的输入与输出之间的关系 B. 找出数据结构的合理性 C. 分析算法的效率以求改进算法 D. 分析算法的可读性与可移植性 5、采用线性链表表示一个向量时,要求占用的存储空间地址(D) A.必须是连续的 B.部分地址必须是连续 C. 一定是不连续的 D. 可连续可不连续 6. 在一个当前长度为n的顺序表中向第j个元素(1next==NULL C、head一>next= = head D、head!=NULL 8、设单链表中指针P指向结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为(A) A、p→next=p→next→next B、p=p→next C、p=p→next→next D、p→next=p 9、若有一个最大长度为size,且设有队首指针front和队尾指针rear的顺序循环队列,试问判断队列满的条件应是下列哪一个语句(D) A、front==rear B、front- rear==size C、front+rear==size; D、front==(rear+1)%size

数据结构试题及答案

数据结构试题 一、单选题(每题 2 分,共20分) 1.1. 对一个算法的评价,不包括如下( B )方面的容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2. 在带有头结点的单链表HL中,要向表头插入一个由指针p 指向的结点,则执行( A )。 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; 3.3. 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4. 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输 出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5. AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6. 采用开放定址法处理散列表的冲突时,其平均查找长度 ( B )。 A.低于法处理冲突 B. 高于法处理冲突 C.与法处理冲突相同 D.高于二分查找 7.7. 若需要利用形参直接访问实参时,应将形参变量说明为( D ) 参数。 A.值 B.函数 C.指针 D.引用 8.8. 在稀疏矩阵的带行指针向量的存储中,每个单链表中的结点 都具有相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9. 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M 对N(M:N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_ 进行。 3. 3. 当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i

相关主题
相关文档 最新文档