《数据结构》形考任务1
一、单项选择题(每小题3分,共60分)
题目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. 输入性
题目8
算法的时间复杂度与()有关。
选择一项:
A. 所使用的计算机
B. 计算机的操作系统
C. 数据结构
D. 算法本身
题目9
设有一个长度为n的顺序表,要在第i个元素之前(也就是插入元素作为新表的第i个元素),插入一个元素,则移动元素个数为()。
选择一项:
A. n-i-1
B. i
题目10
设有一个长度为n的顺序表,要删除第i个元素移动元素的个数为()。
选择一项:
A. i
B. n-i-1
C. n-i
D. n-i+1
题目11
在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句()。
选择一项:
A. p->next=q->next
B. p->next=q
C. p=q->next
D. q->next=NULL
题目12
在一个单链表中p所指结点之后插入一个s所指的结点时,可执行()。
选择一项:
A. p->next=s->next;
B. s->next=p->next; p->next=s;
C. p=s->next
D. p->next= s; s->next= p->next
题目13
非空的单向循环链表的尾结点满足()(设头指针为head,指针p指向尾结点)。
选择一项:
A. p->next==NULL
B. p->next==head
C. p== head
D. p==NULL
题目14
链表不具有的特点是()。
B. 不必事先估计存储空间
C. 可随机访问任一元素
D. 插入删除不需要移动元素
题目15
带头结点的链表为空的判断条件是()(设头指针为head)。
选择一项:
A. head->next==head
B. head->next==NULL
C. head ==NULL
D. head!=NULL
题目16
在一个长度为n的顺序表中为了删除第5个元素,由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为()。
选择一项:
A. 21
B. 25
C. 20
D. 19
题目17
有关线性表的正确说法是()。
选择一项:
A. 除了一个和最后一个元素外,其余元素都有一个且仅有一个直接前驱和一个直接后继
B. 每个元素都有一个直接前驱和一个直接后继
C. 表中的元素必须按由小到大或由大到下排序
D. 线性表至少要求一个元素
题目18
向一个有127个元素的顺序表中插入一个新元素,并保持原来的顺序不变,平均要移动()个元素。
选择一项:
A. 7
B. 63
C. 63.5
一个顺序表第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的地址是()。
选择一项:
A. 102
B. 106
C. 100
D. 98
题目20
在一个不带头结点的单循环链表中,p、q分别指向表中第一个结点和尾结点,现要删除第一个结点,且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p->next;和()。
选择一项:
A. p->next=q
B. q->next=p
C. p=q->next
D. q=p
二、判断题(每小题2分,14题,共28分)
题目21
数据元素可以有一个或多个数据项组成。
选择一项:
对
错
题目22
数据元素之间的抽象关系称为物理结构。
选择一项:
对
错
题目23
数据的逻辑结构在计算机中的表示称为逻辑结构。
选择一项:
对
错
题目24
数据结构中,元素之间存在多对多的关系称为树状结构。
选择一项:
对
错
题目26
通常可以把一本含有不同章节的书的目录结构抽象成线性结构。
选择一项:
对
错
题目27
通常可以把某城市中各公交站点间的线路图抽象成树型结构。
选择一项:
对
错
题目28
设有一个不带头结点的单向循环链表,结点的指针域为next,指针p指向尾结点,现要使p指向第一个结点,可用语句p=p->next;。
选择一项:
对
错
题目29
设有一个单向链表,结点的指针域为next,头指针为head,p指向尾结点,为了使该单向链表改为单向循环链表,可用语句p->next=head 。
选择一项:
对
错
题目30
设有一个单向循环链表,结点的指针域为next,头指针为head,指针p指向表中某结点,若逻辑表达式p->next==head;
要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点,若链表中结点的指针域为next,可执行p->next=s; s->next= p->next;的操作。
选择一项:
对
错
题目32
要在一个单向链表中删除p所指向的结点,已知q指向p所指结点的直接前驱结点,若链表中结点的指针域为next,则可执行q->next= p->next;
选择一项:
对
错
题目33
要在一个带头结点的单向循环链表中删除头结点,得到一个新的不带头结点的单向循环链表,若结点的指针域为next,头指针为head,尾指针为p,则可执行head=head-> next; p->next=head;。
选择一项:
对
错
题目34
设有一个单向循环链表,头指针为head,链表中结点的指针域为next,p指向尾结点的直接前驱结点,若要删除尾结点,得到一个新的单向循环链表,可执行操作p->next=head;。
选择一项:
对
错
三、程序填空题(每小题6分,共12分。请点击正确选项,然后拖拽至相应的方框上)
题目35
设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。
#define NULL 0
p=head; /*p为工作指针*/
do
{printf(“%d\n”, ;
;
}while ;
}
p?>datap=p?>next p!=NULL
题目36
设有一个头指针为head的不带头结点单向链表,p、q是指向链表中结点类型的指针变量,p指向链表中结点a, (设链表中没有结点的数据域与结点a的数据域相同),写出相关语句
(1)使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱
q=p; x=p->data;
while )q=q->next;
q->next=head;
q=p; p=p->next;
while(p->data!=x)
{ q=p;
}
s->next=p;
形考任务2
一、单项选择题(每小题2分,共50分)
题目1
若让元素1,2,3依次进栈,则出栈顺序不可能为()。
C. 2,1,3
D. 1,3,2
题目2
一个队列的入队序列是1,2,3,4。则队列的输出序列是()。
选择一项:
A. 1,4,3,2
B. 4,3,2,1
C. 3,2,4,1
D. 1,2,3,4
题目3
向顺序栈中压入新元素时,应当()。
选择一项:
A. 先后次序无关紧要
B. 先存入元素,再移动栈顶指针
C. 同时进行
D. 先移动栈顶指针,再存入元素
题目4
在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行()。
选择一项:
A. p->next=top->next;top->next=p;
B. p->next=top->next;top=top->next;
C. p->next=top;top=p;
D. top->next=p;
题目5
在一个栈顶指针为top的链栈中删除一个结点时,用 x保存被删结点的值,则执行()。选择一项:
A. x=top->data;top=top->next;
B. top=top->next;x=top->data;
C. x=top->data;
D. x=top;top=top->next;
A. front==rear
B. front==rear+1
C. rear==m-1
D. rear=m
题目7
判断一个循环队列为满的条件是()。
选择一项:
A. rear=MaxSize
B. (rear+1)%MaxSize==front
C. front==rear+1
D. rear%MaxSize= =front
题目8
判断栈满(元素个数最多n个)的条件是()。
选择一项:
A. top==n-1
B. top=-1
C. top!=0
D. top==0
题目9
设有一个20阶的对称矩阵A(第一个元素为a1,1),采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵元素a6,2在一维数组B中的下标是()。
选择一项:
A. 17
B. 28
C. 21
D. 23
题目10
在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区中,而打印机则从缓冲区中取出数据打印,该缓冲区应该是一个()结构。
选择一项:
D. 队列
题目11
一个递归算法必须包括()。
选择一项:
A. 终止条件和迭代部分
B. 递归部分
C. 迭代部分
D. 终止条件和递归部分
题目12
在一个链队中,假设f和r分别为队头和队尾指针,则删除一个结点的运算为()。选择一项:
A. f=f->next;
B. r=r->next;
C. r=f->next;
D. f=r->next;
题目13
在一个链队中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算为()。选择一项:
A. r->next=s;r=s;
B. s->next=f;f=s;
C. s->next=r;r=s;
D. f->next=s;f=s;
题目14
数组a经初始化char a[ ]=“English”;a[7]中存放的是()。
选择一项:
A. "h"
B. 字符h
C. 字符串的结束符
D. 变量h
题目15
A. BCd
B. ABC
C. Bcd
D. Abc
题目16
字符串 a1="AEIJING",a2="AEI",a3="AEFANG",a4="AEFI"中最大的是()。
选择一项:
A. a4
B. a1
C. a3
D. a2
题目17
两个字符串相等的条件是()。
选择一项:
A. 两串包含的字符相同
B. 两串的长度相等
C. 两串的长度相等,并且两串包含的字符相同
D. 两串的长度相等,并且对应位置上的字符相同
题目18
一维数组A采用顺序存储结构,每个元素占用6个字节,第6个元素的存储地址为100,则该数组的首地址是()。选择一项:
A. 70
B. 28
C. 90
D. 64
题目19
一个非空广义表的表头()。
选择一项:
A. 只能是原子
B. 可以是子表或原子
C. 不可能是原子
对稀疏矩阵进行压缩存储,可采用三元组表,一个10 行8列的稀疏矩阵A,其相应的三元组表共有6个元素,矩阵A 共有()个零元素。
选择一项:
A. 10
B. 74
C. 8
D. 72
题目21
对稀疏矩阵进行压缩存储,可采用三元组表,一个10 行8列的稀疏矩阵A共有73个零元素,A的右下角元素为6,其相应的三元组表中的第7个元素是()。
选择一项:
A. (10,8,6)
B. (10,8,7)
C. (7,8,10)
D. (7,10,8)
题目22
对一个栈顶指针为top的链栈进行入栈操作,通过指针变量p生成入栈结点,并给该结点赋值a,则执行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和()。
选择一项:
A. p->next=top;top=p;
B. top->next=p;p=top;
C. p->next=top;p=top;
D. top=top->next;p=top;
题目23
头指针为head的带头结点的单向链表为空的判定条件是()为真。
选择一项:
A. head==NULL
B. head->next==NULL
C. head->next!=NULL
D. head->next!=NULL
题目24
选择一项:
A. 10
B. 5
C. 15
D. 20
题目25
数组a经初始化char a[ ]=“English”;a[1]中存放的是()。
选择一项:
A. "n"
B. "E"
C. 字符n
D. 字符E
二、判断题(每小题2分,16题,共32分)
题目26
设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈,则可执行操作。hs=s;s-> next=hs;
选择一项:
对
错
题目27
设有一个非空的链栈,栈顶指针为hs,要进行出栈操作,用x保存出栈结点的值,栈
结点的指针域为next,则可执行hs=hs->next ;x=hs->data;
选择一项:
对
错
题目28
有一个链栈,栈顶指针为h,现有一个p所指向的结点要入栈,则可执行操作p->next=h; 和h=p;
选择一项:
对
错
域为data,则可执行hs= hs->next; x= hs->data;
选择一项:
对
错
题目30
在一个链队中,f和r分别为队头和队尾指针,队结点的指针域为next,则插入所指结点的操作为r->next=s;r=s;选择一项:
对
错
题目31
在一个链队中,f和r分别为队头和队尾指针,队结点的指针域为next,s指向一个要入队的结点,则入队操作为r=s;r->next=s;
选择一项:
对
错
题目32
在一个不带头结点的非空链队中,f和r分别为队头和队尾指针,队结点的数据域为data,指针域为next,若要进行出队操作,并用变量x存放出队元素的数据值,则相关操作为x=f->data; f=f->next;
选择一项:
对
错
题目33
对稀疏矩阵进行压缩存储,可采用三元组表,一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有34个零元素。
选择一项:
对
错
题目34
循环队列的最大存储空间为MaxSize,队头指针为f,队尾指针为r,当(r+1)%MaxSize=f 时表明队列已满。
选择一项:
对
循环队列的队头指针为f,队尾指针为r,当r= =f时表明队列已满。
选择一项:
对
错
题目36
空串的长度是0;空格串的长度是空格字符的个数。
选择一项:
对
错
题目37
对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标、和非零元素值三项信息。
选择一项:
对
错
题目38
循环队列的引入,目的是为了克服假上溢。
选择一项:
对
错
题目39
设有n阶对称矩阵A,用一维数组s压缩存储A的下三角元素,s的下标从零开始,元素 s[26]相应于A中的元素为a 7,5。选择一项:
对
错
题目40
循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效的判断栈空或栈满,若队头指针front=4,当队尾指针rear=3时队满。
选择一项:
对
错
队尾指针rear=3时,队列中共有5个元素。
选择一项:
对
错
三、程序选择填空题(每小题9分,共18分。请点击正确选项,然后拖拽至相应的方框上)
题目42
以下函数为链栈的进栈操作,x是要进栈的结点的数据域,top为栈顶指针
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc ;
p->data=x;
;
;
}
A.sizeof (struct node) top=p p?>next=top
题目43
以下函数为链队列的入队操作,x为要入队的结点的数据域的值,front、rear分别链队列的队头、队尾指针struct node
{ ElemType data;
struct node *next;
};
struct node *front,*rear;
struct node *p;
p= (struct node*) malloc ;
p->data=x;
p->next=NULL;
;
rear= ;
}
形考任务3
一、单项选择题(每小题2分,共38分)
题目1
假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为()。
选择一项:
A. 47
B. 16
C. 17
D. 15
题目2
二叉树第k层上最多有()个结点。
选择一项:
A. 2k-1
B. 2k-1
C. 2k-1
D. 2k
题目3
将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为()。
选择一项:
A. 36
D. 33
题目4
如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为()。
选择一项:
A. 二叉树
B. 哈夫曼树
C. 完全二叉树
D. 平衡二叉树
题目5
在一棵度具有5层的满二叉树中结点总数为()。
选择一项:
A. 16
B. 32
C. 31
D. 33
题目6
一棵完全二叉树共有6层,且第6层上有6个结点,该树共有()个结点。
选择一项:
A. 31
B. 37
C. 38
D. 72
题目7
利用3、6、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为()。选择一项:
A. 18
B. 16
C. 30
D. 12
题目8
在一棵树中,()没有前驱结点。
B. 叶结点
C. 空结点
D. 分支结点
题目9
设一棵采用链式存储的二叉树,除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空,则该树有()个叶结点。
选择一项:
A. 9
B. 10
C. 21
D. 22
题目10
在一个图G中,所有顶点的度数之和等于所有边数之和的()倍。
选择一项:
A. 2
B. 1
C. 4
D. 1/2
题目11
邻接表是图的一种()。
选择一项:
A. 链式存储结构
B. 顺序存储结构
C. 散列存储结构
D. 索引存储结构
题目12
图的深度优先遍历算法类似于二叉树的()遍历。
选择一项:
A. 先序
B. 后序
C. 层次
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值是 1或T . 2.设P :他生病了,Q :他出差了.R :我同意他不参加学习. 则命题“如 果他生病或出差了,我就同意他不参加学习”符号化的结果为 (P ∨Q )→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) . 4.设P (x ):x 是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ?x(P(x) ∧Q(x)) . 5.设个体域D ={a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) . 6.设个体域D ={1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 0(F) . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 设P :今天是晴天。 姓 名: 学 号: 得 分: 教师签名:
离散数学形成性考核作业( 一) 集合论部分 分校_________ 学号____________________ 姓名__________________ 分数 本课程形成性考核作业共 4 次, 内容由中央电大确定、统一布置。本次形考作业是第一次作业, 大家要认真及时地完成集合论部分的形考作业, 字迹工整, 抄写题目, 解答题有解答过程。 第 1 章集合及其运算 1.用列举法表示”大于2而小于等于9 的整数” 集合. 2.用描述法表示”小于5 的非负整数集合” 集合. 3 .写出集合B={1, {2, 3 }} 的全部子集. 4 .求集合A={ ,{ } } 的幂集. 5 .设集合A={{ a }, a }, 命题: { a } P(A) 是否正确, 说明理由. 6 .设 A {1,2,3}, B { 1,3,5}, C { 2,4,6}, 求 (1) A B (2) A B C (3) C - A (4) A B 7 .化简集合表示式: (( A B ) B) - A B.
试证:A - ( B C ) = ( A - B ) - C. 9 .填写集合{4, 9 } {9, 10, 4} 之间的关系. 10 .设集合A = {2, a , {3}, 4}, 那么下列命题中错误的是() A .{a } A B . { a , 4, {3}} A C . {a } A D . A 11 .设B = { {a }, 3, 4, 2}, 那么下列命题中错误的是() 第2章关系与函数 并验证 A (B C ) = ( A B ) (A C ). 4 .写出从集合A = { a , b , c }到集合B = {1}的所有二元关系. 8 .设A B C 是三个任意集合 A . {a } B B .{2, { a }, 3, 4} B C . {a } B D .设集合A = {a , b }, B = {1, 2, 3}, C = {3, 4}, 求 A (B C ), (A B) (A C ) .对任意三个集合 B 和 C 若ABA C 是否一定有B C ?为什么? .对任意三个集合 B 和 C 试证若A B = AC 」A
326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ),)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ). 5. 设G 是(7, 15)简单平面图,则G 一定是( )图,且其每个面恰由( )条边围成,G 的面数为( ).
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年11月7日前完成并上交任课教师(不收电子稿)。并在03任务界面下方点击“保存”和“交卷”按钮,完成并上交任课教师。 一、填空题 1.设集合{1,2,3},{1,2} ==,则P(A)-P(B )= A B {{3},{2,3},{1,3},{1,2,3}},A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}.2.设集合A有10个元素,那么A的幂集合P(A)的元素个数为1024 .3.设集合A={0, 1, 2, 3},B={2, 3, 4, 5},R是A到B的二元关系, ∈ R? x ∈ > y 且 =且 ∈ < {B , , x A y A y B x } 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}. 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} y y x∈ = < > ∈ x , , x , 2 {B y A 那么R-1={<6,3>,<8,4>} 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
离散数学考试试题(A 卷及答案) 一、(10分)求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解:(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解 设设P :王教授是苏州人;Q :王教授是上海人;R :王教授是杭州人。则根据题意应有: 甲:?P ∧Q 乙:?Q ∧P 丙:?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P ,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为: ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {}f {}c e ,. 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且 不含奇数度结点 . 5.设G=
一、单项选择题(每小题2分,共38分) 题目1 正确 获得2.00分中的2.00分 未标记标记题目 题干 假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为()。 选择一项: A. 16 B. 47 C. 15 D. 17 题目2 正确 获得2.00分中的2.00分 未标记标记题目 题干 二叉树第k层上最多有()个结点。 选择一项: A. 2k-1 B. 2k-1 C. 21 k D. 2k 题目3 正确 获得2.00分中的2.00分 未标记标记题目 题干 将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为()。 选择一项: A. 34 B. 35 C. 33 D. 36 题目4 正确 获得2.00分中的2.00分 未标记标记题目
如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为()。 选择一项: A. 二叉树 B. 哈夫曼树 C. 完全二叉树 D. 平衡二叉树 题目5 正确 获得2.00分中的2.00分 未标记标记题目 题干 在一棵度具有5层的满二叉树中结点总数为()。 选择一项: A. 33 B. 32 C. 31 D. 16 题目6 正确 获得2.00分中的2.00分 未标记标记题目 题干 一棵完全二叉树共有6层,且第6层上有6个结点,该树共有()个结点。 选择一项: A. 37 B. 72 C. 38 D. 31 题目7 正确 获得2.00分中的2.00分 未标记标记题目 题干 利用3、6、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为()。 选择一项: A. 18 B. 30
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ), )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ).
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {}f {}c e ,. 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且 不含奇数度结点 . 5.设G=
计算机科学与技术专业级第二学期离散数学试题 2012年1月 一、单项选择题(每小题3分,本题共15分)1. C 2. C 3. B 4. A 5. D 1-若集合4的元素个数为10,则其幕集的元素个数为()? A. 10 B. 100 C. 1024 D. 1 2. 设A={a, d},伊{1,2}, R、,电、足是刀到8的二元关系,旦用二{<Q, 2>,<。】>},他二{<。 1>,<。2>,<》,】>},足={<。,】>,</?, 2>),则()是从/到8的函数. A. R[和R? B . R仁 C. R3 D. R\和足 3. 设木{1,2,3,45,6,7,8}, /?是/上的整除关系,位{2, 4, 6},则集合8的最大元、最小元、上界、下界依次为()? A. 8、2、8、2 B.无、2、无、2 C. 6、2、6、2 D. 8、1、6、1 4.若完全图G中有77个结点777条边,则当()时,图G中存在欧拉回路. A.。为奇数 B. ”为偶数 C. "7为奇数 D. s为偶数 5.已知图G的邻接矩阵为 % o o 1 T 0 0 0 0 1 0 0 0 1 1 10 10 1 11110 则。有(). A. 6 点,8 边 B.6点,6边 C. 5 点,8 边 D.5点,6边 二、埴空题(每小题3分,本题共15分) 6. 设集合乂 = {况,那么集合/的富集是{。腥}}. 7. 若吊和%是/上的对称关系,则R\U电,R、nw R'-电,传用中对称关系有个. 8. 设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去1 条边后使之变成树. 9. 设连通平面图G的结点数为5,边数为6,贝1|面数为 3 . 10. 设个体域D = G d},则谓词公式(VA)MW A B(X))消去重词后的等值式为(乂(Q) A8(Z?))A(4 (。)AB(/?)) . 三、逻辑公式翻译(每小题6分,本题共12分) 11. 将语句“今天有联欢活动,明天有文艺晚会翻译成命题公式. 设户:今天有联欢活动,Q:明天有文艺晚会,(2分) PN Q.(6 分)
离散数学期末测验试题(有几套带答案1)
————————————————————————————————作者: ————————————————————————————————日期: ?
离散数学试题(A卷及答案) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明:左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分) 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E, ?E→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D)→?E (2) ?E→(A∧?B) ?? (3)(C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) ?? (5) (C∨D)→(R∨S) ? (6) C∨D?? (7) R∨S 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (15分) 证明∵x∈A-(B∪C)?x∈A∧x?(B∪C)?x∈A∧(x?B∧x?C)?(x∈A∧x?B)∧(x∈A∧x?C)?x∈(A-B)∧x∈(A-C)?x∈(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={<x,y>| x,y∈N∧y=x2},S={
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word 文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {f,c} . 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且所有结点的度数全为偶 数 . 5.设G=
2020年电大离散数学(本)期末考试题库及答案 一、单项选择题 1.设P:a是偶数,Q:b是偶数。R:a + b是偶数,则命题“若a是偶数,b是偶数,则a + b 也是偶数”符号化为(D.P Q→R)。2.表达式?x(P(x,y)∨Q(z))∧?y(Q(x,y)→?zQ(z))中?x的辖域是(P(x,y)Q(z))。 3.设) ( }), ({ }, { , 4 3 2 1 ? = ? = ? = ? =P S P S S S则命题为假的是( 4 2 S S∈)。 4.设G是有n个结点的无向完全图,则G的边数(1/2 n(n-1))。 5.设G是连通平面图,有v个结点,e条边,r个面,则r=(e-v+2)。 6.若集合A={1,{2},{1,2}},则下列表述正确的是( {1}?A ). 7.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为( 5 ). 8.设无向图G的邻接矩阵为 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 则G的边数为( 7 ). 9.设集合A={a},则A的幂集为({?,{a}} ). 10.下列公式中(?A∧?B ??(A∨B) )为永真式. 11.若G是一个汉密尔顿图,则G一定是( 连通图). 12.集合A={1, 2, 3, 4}上的关系R={
精品文档院术师范学广东技模拟试题 科目:离散数学 120 分钟考试时间: 考试形式:闭卷 姓名:学号:系别、班级: 2分,共10分)一.填空题(每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____,,2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________,则3. 设__ , b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统(N,+)中,其单位元是0,仅有_1___ 有逆元。 ne条边,则G有___e+2-n____个面。5.如果连通平面图G有个顶点,二.选择题(每小题2分,共10分) P?(Q?R)等价的公式是(1. 与命题公式) (A)(B)(C)(D)R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 (A)(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档. 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三.计算题(共43分) p?q?r的主合取范式与主析取范式。(1. 求命题公式6分) 解:主合取方式:p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式:p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵,并画出分)10(,
电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题 1.设集合{1,2,3},{1,2} A B ==,P(A)-P(B )={{3},{1,3},{2,3},{1,2,3}},A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} . 2.设集合A有10个元素,那么A的幂集合P(A)的元素个数为 1024 .
3.设集合A={0, 1, 2, 3},B={2, 3, 4, 5},R是A到B的二元关系, 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}. 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} x∈ y y > <那么R-1={<6,3>,<8,4>}. x = ∈ 2 , , x , {B A y 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
北京工业大学经管学院期末试卷 《离散数学》(A) 学号姓名:成绩 一、单项选择题(每题2分,共18分) 1.令P:今天下雪了,Q:路滑,则命题“虽然今天下雪了,但是路不.滑”可符号化为(D)A.P→Q B.P∨Q C.P∧Q D.P∧Q p→q,蕴涵式,表示假设、条件、“如果,就”。 “→”与此题无关 2. 关于命题变元P和Q的极大项M1表示( C )。书P1520,此题换作p、q更容易理解 A.┐P∧Q B.┐P∨Q p∨┐q 01 1 M1 ∨┐Q∧┐Q 3.设R(x):x是实数;S():x小于y。用谓词表达下述命题:不存在最小的实数。其中错误的表达式是:(D) 4.在论域{}中与公式(x?)A(x)等价的不含存在量词的公式是(B) A.)b( )a( A∨ A A )a( A∧ B. )b( C. )b( )b( A→ A A )a( A→ D. )a( 5.下列命题公式为重言式的是(C) A.Q→(P∧Q)B.P→(P∧Q) C.(P∧Q)→P D.(P∨Q)→Q 牢记→真假条件,作为选择题可直接代入0、1,使选项出现1→0,排除。熟练的可直接看出C不存在1→0的情况 6. 设{1,2,3},{},下列二元关系R为A到B的函数的是( A ) A. {<1>,<2>,<3>} B. {<1>,<2>} C. {<1>,<1>,<2>,<3>} D. {<1>,<2>,<3>,<1>} 7.偏序关系具有性质(D)背
A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合,映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f :A→B (1)若,则f 是满射的【即值域为B 的全集,在本题中为R ,该二次函数有最高点,不满足】 (2)若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2),则称f 是单射的【即真正一一对应,甚至不存在一个y 对应多个x 。显然,本题为二次函数,不满足】 (3)若f 既是满射的,又是单射的,则称f 是双射的【本题中两个都不满足,既不是单射也不是满射】 二、填空题(每空2分,共22分) 1.设Q 为有理数集,笛卡尔集×Q ,*是S 上的二元运算,?,
五、证明题 1.设G 是一个n 阶无向简单图,n 是大于等于3的奇数.证明图G 与它的补图G 中的奇数度顶点个数相等. 证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边删去E 所得到的.所以对于任意结 点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于3的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等. 2.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图. 证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数. 又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图. 故最少要加2 k 条边到图G 才能使其成为欧拉图. 五、证明题 1.试证明集合等式:A ? (B ?C )=(A ?B ) ? (A ?C ). 证:若x ∈A ? (B ?C ),则x ∈A 或x ∈B ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C . 即x ∈A ?B 且x ∈A ?C , 即x ∈T =(A ?B ) ? (A ?C ), 所以A ? (B ?C )? (A ?B ) ? (A ?C ). 反之,若x ∈(A ?B ) ? (A ?C ),则x ∈A ?B 且x ∈A ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C , 即x ∈A 或x ∈B ?C , 即x ∈A ? (B ?C ), 所以(A ?B ) ? (A ?C )? A ? (B ?C ). 因此.A ? (B ?C )=(A ?B ) ? (A ?C ). 2.对任意三个集合A , B 和C ,试证明:若A ?B = A ?C ,且A ≠?,则B = C . 证明:设x ∈A ,y ∈B ,则